Быстрые операции над многочленами ч.1. (6 февраля 2025)

1. Задачи на производящие функции
   1. 3-SUM за O(SlogS)
   2. Счастливые билеты
   3. n! за O(n^1/2) ⇒ факторизация за n^1/4
   4. Рюкзак за O(SlogS + n) (затравка)
   
   
2. Операции с многочленами через разделяйку
   1. Перевод из одной системы в другую
   2. Деление
   3. Multipoint Evaluation
   4. Any points Interpolation
   
   
3. За сколько вообще можно умножать многочлены?
   1. Над F₂: bitset
   2. Над кольцом: Карацуба
   3. Над F₂: спарим bitset и Карацубу
   
   
4. Вспоминаем FFT
   1. Общая схема: FFT(A), FFT(B), умножить поточечно, FFT^-1
   2. Комплексные корни из единицы: картинка, группа, умножения и степени
   3. Рекурсивное FFT: идея + реализация
   4. Задача на понимания 1: считаем 2ⁿ − nlogn или nlog²n?

1. Более подробный план того, что выше:
   
   
2. 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) = (k²)!, чтобы дополнить до n!, сделаем руками O(k) умножений, время работы: O(n^1/2log²n)
   3. Посчитать P(x) мы можем через разделяй и властвуй за O(klog²k)
   4. Умножение нужно теперь делать не в C, а по модулю m. Умножим в Z (то же, что R, что C), в конце возьмём по модулю m.
   5. Факторизация. min d: gcd(d!, n) != 1 - минимальный делитель n. Можно бинпоиском, можно "двоичными подъёмами" за O(n^1/4log²n)
   
   
3. Разделяй и властвуй для интерполяции
   1. Ньютон: (x₁...x_n-1, y₁...y_n-1) → P(x) → P(x) + Q(x)/Q(x_n)*(y_n - P(x_n)), где Q(x) = (x-x₁)(x-x₂)...(x-x_n-1)
   2. Разделяй и властвуй: (x₁...x_n/2, y₁...y_n/2) → P(x) → P(x) + Q(x)*S(x), (x-x₁)(x-x₂)...(x-x_n/2), а
      значения S(x) в точках x_n/2+1...x_n вычисляются как S(x_i) = (y_i - P(x_i)) / Q(x_i)
   
   
4. Где почитать? Лекция от sankowski