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

1. Действия над F₂ (bitset, разминка)
   1. Умножение за O(nm/w): с = a << i
   2. Деление за O((n-m)m/w): с[i] = 1; a = b << i
   3. gcd за O(nm/w) // (n+m)min(n,m) = Θ(nm)
   
   
2. Умножение многочленов
   1. Над F₂ = O(nm/w)
   2. Над произвольным кольцом есть O(nm) и Карацуба O(n^log₂(3)) ~= n^1.58
   3. Над комплексными числами (значит, и R, и Z) есть FFT за O(nlogn) (повторим/изучим позже)
   
   
3. Упражнение: 3SUM − n чисел от -m до m, выбрать 3 с суммой 0
   
   
4. Разделяй и властвуй
   1. Перевод из одной системы счисления в другую за logn умножений
   2. Деление за logn умножений : nlog²n (ссылка на будущее и nlogn)
   
   
5. Деление за nlog²n: подробности
   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,k) : |A|=|B|=k
   5. Разделяй и властвуй: Div(A,B,n): C₁ = Div(A,B,n/2), C₂ = Div(A-BC₁,B,n/2), return concat(C₁, C₂)
   6. Время работы T(n) = 2T(n/2) + Mul(n) = или O(nlog²n), или O(n^log₂(3)) в зависимости от реализации Mul
   
   
6. Разделяй и властвуй для вычисления значения многочленов в точках (evaluation) за logn делений : nlog³n
   1. P(x₀) = P(x) mod (x - x₀); Q(x) = P(x) mod (x - x₁)(x - x₂)...(x - x_k) ⇒ Q(x_i) = P(x_i)
   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(klog²k)
   
   
7. Разделяй и властвуй для интерполяции
   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)
   
   
8. [skipped] Извлечение корня за logn делений
   
   
9. 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)
   
   
10. FFT (напоминание)
    1. Общая схема: FFT(A), FFT(B), умножить поточечно, FFT^-1
    2. Комплексные корни из единицы: картинка, группа, умножения и степени
    3. Рекурсивное FFT: идея + реализация
    4. Тренировка понимания 1: считаем 2ⁿ − nlogn или nlog²n?
    5. Тренировка понимания 2: перевод между системами счисления − nlogn или nlog²n?
    
    
11. Где почитать? Лекция от sankowski

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

1. Разминка: число счастливых билетов из 2n цифр
   1. P(x) = (x⁰ + x¹ + ... + x^d)ⁿ, ответ = сумма квадратов коэффициентов P(x)
   2. N = dn ⇒ возведение в степень работает за O(mul(N)) = O(NlogN)
   
   
2. Применения 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. Рюкзак, subsetsum за O~(n^1/2S)
   
   
3. Соединяем умножения над F₂ − bitset и Карацубу
   1. Рекурсия Карацубы, когда n ≤ w, можно умножить за n²/w = O(w), оптимизация в w^log(3)-1 раз
   2. Рекурсия Карацубы, при подъёме сложение и вычитания превратились в xor за O(n/w), оптимизация в w раз
   3. Но время Карацубы будет T(n/w)*w, где T(n) = 3T(n/2) + 1 = w(n/w)^log₂(3) = n^log₂(3) / w^log₂(3)-1
   
   
4. Умножение многочленов не в C
   1. Над кольцом Z/mZ, m − простое вида x*2^s+1, n < 2^s.
   2. Над Z (лучше всего по КТО для разных Z/mZ)
   
   
5. Быстрая нерекурсивная версия FFT
   1. Предподсчёт корней root[i] = (cos,sin)
   2. Прямой ход рекурсии − перестановка массива коэффициентов A: F[rev[i]] = A[i], rev[i] = rev[i/2]/2 + ((i%2) << (k-1))
   3. Обратный ход рекурсии − 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] = ...; }}
   
   
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 (обращение ряда)
   
   
7. Метод Ньютона и применение FFT к длинным числам
   1. Деление длинных чисел за O(nlogn)
   2. Извлечение корня за O(nlogn)