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

1. Простые вопросы про FFT
   1. За сколько мы умеем посчитать 2ⁿ?
   
   
2. Умножение многочленов не в C
   1. Умножение над F₂: спарим bitset и Карацубу
   2. Над кольцом Z/mZ, m − простое вида x*2^s+1, n < 2^s.
   3. Над Z (лучше всего по КТО для разных Z/mZ)
   
   
   
3. Вспоминаем FFT
   1. Рекурсивное FFT: идея + реализация
   2. Предподсчёт корней root[i] = (cos,sin)
   3. Прямой ход рекурсии − перестановка массива коэффициентов A: F[rev[i]] = A[i], rev[i] = rev[i/2]/2 + ((i%2) << (k-1))
   4. Обратный ход рекурсии − FOR (s=0..k-2) { n = 2^s; FOR (t=0; t<N; t+=2n) FOR (j=0; j<n; j++) { tmp = ...; F[t+j+n] = ...; F[t+j] = ...; }}
   
   
4. Метод Ньютона и действия с рядами
   1. x → (x+a/x)/2 (корень для чисел); Картинка метода Ньютона; шаг x → x - f'/f
   2. Оценка скорости сходимости Ньютона
   3. Ньютон для чисел 1/x
   4. Ньютон для чисел x^1/2
   5. Ньютон для обратного ряда
   6. Деление длинных чисел и извлечение корня за O(nlogn)
   7. Дифференцирование/интегрирование: a_k → k*a_k
   8. Логарифм ряда
   9. Ньютон для экспоненты
   
   
5. Применения FFT
   1. Умножение многочленов от двух переменных xⁱy^j (y = xⁿ ⇒ nmlog(nm))
   2. Покраска в k цветов (∑_{I независимо} x^Iy^|I|) : предподсчитали независимые за 2ⁿ, возводим в степень k за k умножений: O(k2ⁿn²)
   3. Рюкзак, subsetsum+количество: набрать ровно k предметов с суммой ровно S за O(nSlogSlogn) (разделяйка, внутри fft: T(n,S) = 2T(n/2,S) + nS*log)
   4. [skipped] Рюкзак, subsetsum за O~(n^1/2S)
   
   
6. Деление многочленов за O(nlogn)
   1. reverse(A) = A^R, заметим, что (BC)^R = B^RC^R
   2. Определение деления новыми словами. A, B → C: A^R = (BC)^R mod xⁿ
   3. Обращение ряда: получаем n первых членов обратного к A, за O(Mul(n)) AA^-1 = 1 mod xⁿ
   4. Получаем C^R = (B^R)^-1A^R (обращение ряда)