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

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

<br>
# FFT
## Ликбез по комплексным числам: умножение, деление, векторное представление, корни из единицы
## Схема умножение: 2^n &ge; k_1 + k_2 + 1, вычисление значения многочленов в точке, интерполяция
## Вопрос: можно ли такой схемой делить? (ответ: только нацело)
## FFT: рекурсивная схема
## FFT: рекурсивный псевдокод
## FFT: нерекурсивный оптимальный псевдокод (удаляем обратный ход рекурсии, разворачиваем циклы)
## Вычисление и хранение корней (root[k+j] = j-й корень по основания 2^k)
## Обратное FFT, сводим к прямому
## Уможение чисел: два веществененных в одном 
## Уможение чисел: выбор системы счисления (ответ = 10^5)

<br>
# Задачи
## Скалярные проиозведение
## Поиск в тексте с ? строки с ?
## Перевод из одной системы счисления в другую за O(nlog^2n)
## Поиск картинки, минимизация среднеквадратичного отклонения

<br>
# Дополнение
## Умножение многочленов с коэффициентами до 10^9 по модулю 10^9+7 за 3 FFT
## Умножение не в комплесных, а в целых по модулю

