## ЛКШ 2018, 10-й день, FFT (Сергей Копелиович)

1. Длинная арифметика

1. Хранение от мл к ст. Сложение, вычитание, умножение/деление на короткое. Всё за O(n). BASE = 109.
2. Умножение и деление многочленов за O(nm)
3. Умножение и деление за O(nm/k2), где BASE = 10k.
4. Двоичная арифметика: умножение, деление, gcd

2. FFT

1. Ликбез по комплексным числам: умножение, деление, векторное представление, корни из единицы
2. Схема умножение: 2n ≥ k1 + k2 + 1, вычисление значения многочленов в точке, интерполяция
3. Вопрос: можно ли такой схемой делить? (ответ: только нацело)
4. FFT: рекурсивная схема
5. FFT: рекурсивный псевдокод
6. FFT: нерекурсивный оптимальный псевдокод (удаляем обратный ход рекурсии, разворачиваем циклы)
7. Вычисление и хранение корней (root[k+j] = j-й корень по основания 2k)
8. Обратное FFT, сводим к прямому
9. Уможение чисел: два веществененных в одном
10. Уможение чисел: выбор системы счисления (ответ = 105)

3. Задачи

1. Скалярные проиозведение
2. Поиск в тексте с ? строки с ?
3. Перевод из одной системы счисления в другую за O(nlog2n)
4. Поиск картинки, минимизация среднеквадратичного отклонения

4. Дополнение

1. Умножение многочленов с коэффициентами до 109 по модулю 109+7 за 3 FFT
2. Умножение не в комплесных, а в целых по модулю