ЛКШ 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. Умножение не в комплесных, а в целых по модулю