Конспект: быстрое преобразование Фурье

Понятия

Корень из единицы - число ω, у которого ω^n = 1. Комплексный: ω = e^(2πi/n). По модулю: ω = g^((p−1)/n), где g - первообразный корень.

Бабочка - пара операций, дающая из одних E и O сразу два значения: одно сложением, другое вычитанием.

Свёртка - c[k] = Σ a[i]·b[k−i]. Умножение многочленов - её частный случай.

Что унести

Два представления одного многочлена степени n−1:

Переход между ними по n произвольным точкам стоил бы Θ(n²). В корнях из единицы - Θ(n·log n), и на этом стоит весь алгоритм.

A(x) = E(x²) + x·O(x²)          E - чётные коэффициенты, O - нечётные

A(ω^k)        = E(ω^{2k}) + ω^k·O(ω^{2k})
A(ω^{k+n/2})  = E(ω^{2k}) − ω^k·O(ω^{2k})       так как ω^{k+n/2} = −ω^k

T(n) = 2·T(n/2) + n   →   Θ(n·log n)

Почему работает: (ω^k)² пробегает ровно n/2 корней порядка n/2 - набор самоподобен.

Обратное преобразование - тот же алгоритм с ω^{−1} и делением на n: обратная матрица равна W⁻¹[j][k] = ω^{−jk}/n, потому что Σ_k ω^{(j−m)k} равна n при j = m и нулю иначе.

УМНОЖИТЬ ДВА МНОГОЧЛЕНА (= посчитать свёртку)
1. дополнить нулями до степени двойки n ≥ len(a)+len(b)−1
2. A = fft(a), B = fft(b)
3. C[j] = A[j]·B[j]
4. c = ifft(C)

Модули для NTT: 998244353 = 7·17·2^23 + 1 (корень 3, длина до 2^23), 65537 = 2^16 + 1 (корень 3, длина до 2^16).

К свёртке сводятся: умножение длинных чисел (цифры как коэффициенты плюс переносы), все суммы двух множеств (свёртка индикаторов - и сразу с числом способов), распределение суммы величин, скользящее среднее, размытие картинки, поиск с джокерами, число пар с заданной разностью.

Тихие ошибки: длина без запаса на полный результат - получится ЦИКЛИЧЕСКАЯ свёртка, ответ неверен без ошибки в коде; забыть поделить на n в обратном; перепутать ω и ω^{−1}; ждать целых от комплексного БПФ; применять преобразование к сотне элементов, где лоб быстрее; перенести код NTT с модулем 998244353 в JavaScript или Python-под-double, где произведение 10¹⁸ уже не точно.

Порог выгоды замеряют, а не вычисляют: у преобразования большая константа, и на малых n свёртка в лоб быстрее.

Куда это ведёт

Раздел «Разделяй и властвуй» на этом закончен: от общей схемы и трёх режимов её цены через экономию одного умножения (Карацуба, Штрассен) и геометрию (ближайшая пара) - к пределу, где объединение почти бесплатно. Дальше - жадные алгоритмы: приём, который чаще всего неверен, и два способа доказать, что в конкретном случае он всё-таки верен.