Быстрые операции над многочленами ч.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?