FFT (3-е апреля 2019)

  1. Соединяем умножения над F2 - bitset и Карацубу
    1. Рекурсия Карацубы, когда n ≤ w, можно умножить за n2/w = O(w), оптимизация в wlog(3)-1 раз
    2. Рекурсия Карацубы, при подъёме сложение и вычитания превратились в xor за O(n/w), оптимизация в w раз
    3. Но время Карацубы будет T(n/w)*w, где T(n) = 3T(n/2) + 1 = w(n/w)log2(3) = nlog2(3) / wlog2(3)-1

  2. FFT над комплексными числами
    1. Схема умножения многочленов: FFT(A), FFT(B), умножить поточечно, FFT-1
    2. Рекурсивная схема FFT.
    3. Прямой ход рекурсии - перестановка массива коэффициентов A: F[rev[i]] = A[i], rev[i] = rev[i/2]/2 + ((i%2) << (k-1))
    4. Обратный ход рекурсии - FOR (s=0..k-2) { n = 2s; FOR (t=0; t<N; t+=2n) FOR (j=0; j<n; j++) { tmp = ...; F[t+j+n] = ...; F[t+j] = ...; }}

  3. Разделяй и властвуй для вычисления значения многочленов в точках
    1. P(x0) = P(x) mod (x - x0); Q(x) = P(x) mod (x - x1)(x - x2)...(x - xk) ⇒ Q(xi) = P(xi)
    2. eval(P, x1, ... xk) = eval(P mod (x - x1)...(x - xk/2), x1, ... xk/2), eval(P mod (x - xk/2+1)...(x - xk), xk/2+1, ... xk)
    3. Время работы: T(k) = 2T(k/2) + Div(k) = O(klog2k)

  4. n! mod m
    1. k = floor(sqrt(n)), рассмотрим P(x) = x(x+k)(x+2k)...(x+k(k-1))
    2. P(1)P(2)P(3)...P(k) = (k2)!, чтобы дополнить до n!, сделаем руками O(k) умножений, время работы: O(n1/2log2n)
    3. Посчитать P(x) мы можем разделяй и властвуй за O(klog2k)
    4. Умножение нужно теперь делать не в C, а по модулю m. Умножим в Z (то же, что R, что C), в конце возьмём по модулю m.
    5. Если не хватает точности обычного вещественного типа (m = 109 ⇒ long double уже слишком мал), то представим многочлен с коэф до m,
      как сумму двух с коэф до m1/2: P(x) = P1(x) + m1/2P2(x) и сделаем 3 умножения, как в Карацубе
    6. Факторизация. min d: gcd(d!, n) != 1 - минимальный делитель n. Можно бинпоиском, можно "двоичными подъёмами" за O(n1/4log2n)