Фурье

1. Чтобы перемножить многочлены: A, B → F(A), F(B) → F(C)=F(A)*F(B) → C
2. Нужно научиться интерполировать и экстерполировать. Научимся считать значение в точках k=0..n-1, z[k]=(cos(2πk/n), sin(2πk/n))
3. Решаем рекурсивно т.к. любой многочлен P(x) можно разбить на четные и нечетные степени: P(x) = A(x²) + x*B(x²).
4. Получили алгоритм прямого преобразования (экстерполяции) за O(NlogN). A --> FFT(A)
5. Обратное преобразование в теории. Есть система уравнений и факт, что z[0]^k+z[1]^k+...+z[n-1]^k == 0, если k = 1..N-1. Решаем систему.
6. Обратное преобразование на практике: B := FFT(A). C := FFT(B). D := C.reverse(2,N). E := D/N. Утверждается, что A == E.

Оптимизации - нужно рассказывать, уже после того, как человек закодил Фурье.

1. Сделаем мало умножений (в 2 раза меньше, т.к. w^n/2 = -1).
2. Раздвоение (2 прямых в одном).
3. Нерекурсивная реализация (рекурсия = спуск за O(NlogN) + подъем за O(NlogN), оставим только подъем).
4. Нерекурсивная реализация. Реверс битов. Rev[a] = Rev[a / 2] / 2 + ((a & 1) << (N - 1))
5. Еще лучше так: 0.5 * (Рекурсия + Нерекурсивная реализация)
6. Зацикливание массива в задаче 110304a1 : 3A (т.к. длина всегда ровно 2ⁿ).

Практика

1. Напишите Фурье. 110304a1 : 3L
2. Решите хоть одну задачку с помощью Фурье. 110304a1 : 3K
3. Напишите Раздвоение. 110304a1 : 3H
4. Напишите Фурье по простому модулю. 110304a1 : 3F
5. Решите и соптимизьте. 110304a1 : 3A
6. Решите и соптимизьте. 110304a1 : 3D

Код

1. Короткая реализация Фурье от Burunduk1. [link]