FFT (9 декабря 2024)

1. Примеры
   1. a, b: c_n = ∑_i a_ib_n-i
   2. Рюкзак, выбрать цифры, чтобы сумма была S (только формула)
   3. Количество счастливых билетов (только формула)
   4. Выбрать из трёх массивов по числу, чтобы сумма была S.
   
   
2. Что мы умеем с многочленами
   1. Сложение, вычитание. Умножение за квадрат. Умножение Карацубой.
   2. Деление многочленов за O((n-m)m) с реализацией.
   
   
3. FFT
   1. Извлечение корня из комплексного числа, единственность интерполяционного многочлена и интерполяция за O(n²)
   2. Схема умножение многочленов
   3. Рекурсивное вычисление FFT за O(nlogn) (над комплексными числами)
   4. Нерекурсивная оптимизированная реализация, обратная битовая запись.
   5. Связь обратного FFT и прямого FFT. Вычисление обратного за O(nlogn) (через w^-1, через reverse, через обратную посл. действий)
   6. Оптимизация: два вещественных FFT в одном комплексном
   7. Погрешность: вычисление корней
   
   
4. Быстрая длинная арифметика
   1. FFT для многочленов: ограничение на коэффициенты для комплексного случая
   2. Умножение чисел за O(nlogn), выбор системы счисления
   3. Сложение, вычитание, сравнение, умножение на короткое, деление на короткое
   4. gcd