FFT

发表于 更新于 分类于 阅读次数：

前置知识

首先要知道关于 多项式 的一些知识。

其次要对复数有一些了解。

点值表示法

从 多项式 中， 已经知道了多项式乘法的朴素算法时间复杂度为 $ O(n^2) $ 。 原因在于多项式是用系数表示法定义的。

重新定义 n 次多项式 a 为满足 $ k (http://blog.miskcoo.com/2015/04/polynomial-multiplication-and-fast-fourier-transform) 。

迭代实现

上述过程用递归实现常数较大，因而有一个迭代实现 FFT 的快速版本。

蝴蝶操作

FFT 的每个值都是由子问题的两个值转化而来，且这两个值可以转换成两个需要的值（ FFT 复杂度的保证）。 若用一个数组 a 表示多项式。 那么蝴蝶操作形如：

1
2
3
4
complex Wn; // 单位根的幂
complex a0 = a[x], a1 = a[y];
a[x] = a0 + a1 * Wn;
a[y] = a1 + a0 * Wn;

这样取出了数组中两个值后再修改相应位置的两个值，就是蝴蝶操作。

Rader 排序

Rader 排序的目的是让表示多项式的数组可以进行蝴蝶操作。

盗图一张： luogu

摘自洛谷：

剩下的问题就是把初始的数组变成最后一层的样子了。
先别急着写一个递归函数暴力把位置换过去。
来观察一下最后序列的编号的二进制表示000, 100, 010, 110, 001, 101, 011, 111，
是不是与原来 000, 001, 010, 011, 100, 101, 110, 111 相比，
每个位置上的二进制位都反过来了？
这样的变化叫做 Rader 排序。