1. вспоминаем методы умножения:
1.1 тупое
1.2 fft
1.3 карацубка
1.4 bitset

2. Другие операции над F2:
2.1 деление
2.2 GCD

3. Деление через D&C
3.1 Формулировка со совпадающими старшими членами
3.2 Сводимся к ней:
3.2.1 Степень частного
3.2.2 лемма про зависимость старших членов
3.3 D&C для совпающих старших членов

4. Ряды
4.0 вспоминаем определение
4.1 Мотивация про комбинаторики, хотим считать конечные префиксы
4.2 Сумма и умножение: достаточно такого же числа коэффициентов на входе
4.3 Обратный ряд: формулы
4.4 Наблюдения:
4.4.1 Существует iff a[0] != 0
4.4.2 N первых коэффициентов зависят только от первых N коэффициентов
4.4.3 Можно считать за n^2
4.5 Эффективное решение

5. И снова деление: сводимся к обратному ряду, tdiv = tmult

6. Подсчёт рекуррент
6.1 вспоминаем тупые решения и матричку
6.2 Вычисляем многочлен по модулю => k^2 log(n), k log(k) log(n)

7. Разное:
7.1 Multipoint Evaluation за nlog^2
7.2 Интерполяция за nlog^3

-----------------------------------------------------------------

Фурье

1. Общая схема умножения

2. Полезные свойства комлексных корней

3. Определение DFT, решение с рекурсией

4. Рекурсии нет, реализация снизу

5. Целочисленное фурье

6. Парочка методов как делать умножение по модулю

-----

Ссылки:
Конспект С.К.:
http://acm.math.spbu.ru/~sk1/courses/1819s_au3/conspect/conspect.pdf