Операции над многочленами (1-е апреля 2019)

1. Действия над F₂ (разминка)
1. Умножение за O(nm/w)
2. Деление за O((n-m)m/w)
3. gcd за O(nm/w) // (n+m)min(n,m) = Θ(nm)


2. Умножение многочленов
1. Над F₂ = O(nm/w)
2. Над произвольным кольцом есть O(nm) и Карацуба O(n^log₂(3))
3. Над комплексными числами (а, значит, и R, и Z) есть FFT за O(nlogn)


3. Деление многочленов
1. Определение деления: хотим из A длины n и B длины n получить такой C длины n, что у A и BC совпадают n старших коэффициентов
2. Основная лемма: старшие k С зависят только от старших k A и старших k B
3. Деление за квадрат: c_n-1 = a_n-1/b_n-1, c_i = (a_i - c_n-1b_i - c_n-2b_i+1 - ...) / b_n-1
4. Разделяй и властвуй: Div(A,B,n): C₁ = Div(A,B,n/2), C₂ = Div(A-BC₁,B,n/2), return concat(C₁, C₂)
5. Время работы T(n) = 2T(n/2) + Mul(n) = или O(nlog²n), или O(n^log₂(3)) в зависимости от реализации Mul


4. Деление многочленов за 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 (обращение ряда)