（Tip：如果想真正完全弄懂FFTの本质，建议首先去理解傅里叶变换的物理本质以及DFT，这里只是我为了满足算法竞赛的要求的初步学习总结，其实我还是有点懵的

多项式的系数乘法

给定两个多项式：

$A(x)=a_0+a_1x+\cdots+a_{n-1}x^{n-1}$

$B(x)=b_0+b_1x+\cdots+b_{n-1}x^{n-1}$

其相乘结果为：

$C(x)=c_0+c_1x+\cdots+c_{n-1}x^{2n-2}$

不难发现，如果使用纯系数乘法，时间复杂度是 $O(n^2)$ 的.

点值乘法

性质1：一个$n$次多项式可以用$n$个点来表示，即点值与多项式的系数存在映射关系.

因此我们可以构造 $2n-1$ 个 $x_i$，分别代入求点值 $O(n^2)$：

$A(x): y_0,y_1,\cdots,y_{2n-2}$

$B(x): y_0^{,},y_1^{,},\cdots,y_{2n-2}^{,}$

然后相乘：

$C(x):y_0y_0^{,},y_1y_1^{,},\cdots,y_{2n-2}y_{2n-2}^{,}$

通过插值转化为系数 $O(n^2)$：

$C(x):c_0,c_1,\cdots,c_{2n-2}$

可以发现，如果使用暴力的做法，代入点值以及插值的时间复杂度依然是 $O(n^2)$

FFT 正变换

通过代入复数单位根及其范围内的$k$次幂，可以将代入点值这一步简化为 $O(n \log n)$

首先规定多项式次数 $n=2^{b \in \mathbb{N}}$, 这样我们就可以把复平面上的单位圆进行 $n$ 等分（并满足许多有用的性质），这样就可以得到方程 $(\cos \theta + i\sin \theta)^n = 1$ 的 $n$ 个复数根.

为什么呢？我们定义第$k$个根为 $\omega_n^k=\cos\frac{2\pi k}{n} + i\sin\frac{2\pi k}{n}$

其满足：$\omega_n^k \omega_n^m = \omega_n^{k+m}, (\omega_n^k)^m=\omega_n^{km}$

周期性：$\omega_n^k=\omega_n^{k+n}$

因此，对于单位根 $\omega_n$ 进行 $n$ 次自乘，发现还是等于自己.

当然，对于所有的 $\omega_n^k$ 也都是一样，且它们皆不相同，因此方程的 $n$ 个解就是这些.

另外其拥有对称性 $\omega_n^{k+\frac{n}{2}} = -\omega_n^k$ 以及折半性 $\omega_n^{2k}=\omega_{\frac{n}{2}}^k$

其中折半性使问题可以递归分治求解

考虑多项式 $A(x)=a_0+a_1x+\cdots+a_{n-1}x^{n-1}$, 提取出其奇偶项：

$A_1(x)=a_0+a_2x+\cdots+a_{n-2}x^{\frac{n}{2}-1}$

$A_2(x)=a_1+a_3x+\cdots+a_{n-1}x^{\frac{n}{2}-1}$

则 $A(x)=A_1(x^2)+xA_2(x^2)$

我们将 $\omega_n^k$ 中 $k < \frac{n}{2}$ 的部分代入：

$A(\omega_n^k)=A_1(\omega_n^{2k})+\omega_n^k A_2(\omega_n^{2k})=A_1(\omega_{\frac{n}{2}}^{k})+\omega_n^k A_2(\omega_{\frac{n}{2}}^{k})$

再将后半部分复数根代入：

$A(\omega_n^{k+\frac{n}{2}})=A_1(\omega_n^{2k+n})+\omega_n^{k+\frac{n}{2}} A_2(\omega_n^{2k+n})=A_1(\omega_{\frac{n}{2}}^{k})-\omega_n^k A_2(\omega_{\frac{n}{2}}^{k})$

我们发现，可以将问题规模为 $n$ 转化为问题规模为 $\frac{n}{2}$, 因此该问题可以递归求解. 每一步递归需要将系数分为奇偶两部分，例如：

$\mathrm{step}1: (a_0,a_1,a_2,a_3,a_4,a_5,a_6,a_7)$

$\mathrm{step}2: (a_0,a_2,a_4,a_6)(a_1,a_3,a_5,a_7)$

$\mathrm{step}3: (a_0,a_4)(a_2,a_6)(a_1,a_5)(a_3,a_7)$

到达递归底部时，直接return.

递归执行完两部分的任务时，可以直接根据上述推导柿子来计算当前这一层即可.

IFFT 逆变换

将多项式A和B进行FFT正变换后进行 $O(n)$ 相乘得到多项式C的 $2n-1$ 个点值$(y_0,y_1,\cdots,y_{2n-1})$

其中 $y_i=\sum_{j=0}^{2n-1}c_j(\omega_n^i)^j$

将这些点值作为系数构造多项式 $D(x)=y_0+y_1x+\cdots+y_{2n-1}x^{2n-1}$

把所有单位根的倒数 $\omega_n^0,\omega_n^{-1},\cdots$ 代入，得到 $2n-1$ 个新点值 $z_0,z_1,\cdots$

其中 $z_k=\sum_{i=0}^{2n-1}y_i(\omega_n^{-k})^i=\sum_{i=0}^{2n-1}\sum_{j=0}^{2n-1}c_j(\omega_n^i)^j(\omega_n^{-k})^i=\sum_{j=0}^{2n-1}c_j\sum_{i=0}^{2n-1}(\omega_n^{j-k})^i$

观察 $\sum_{i=0}^{2n-1}(\omega_n^{j-k})^i$, 当 $j=k$ 时，内层和式为 $2n$

$当 j \neq k$ 时，内层是个等比数列，运用求和公式可以得到其值为0

所以 $z_k=(2n)c_k$, 为方便直接令这里的 $2n$ 为 $n$ (完蛋，好像正变换一直用的是 $n$ 不是 $2n$，但其实无所谓，知道要取多少个复数根就行)，得到 $c_k=\frac{z_k}{n}$

现在考虑 $\omega_n^{-k}$, 其等于 $\cos \theta - i\sin \theta$, 其等价于虚部变负

因此 FFT 和 IFFT 完全可以合并成一个函数，只需控制单位根 $\omega_n$ 的虚部即可.

非递归の实现

观察原序列的二进制形式：

$(000,001,010,011,100,101,110,111)$

以及递归底层变换后的：

$(000,100,010,110,001,101,011,111)$

可以发现对应的二进制进行了翻转操作. 我们只需将原有系数的位置调换到其正确的位置，然后通过枚举层数来自底向上归并.

设 $F(x)$ 为其翻转后的数，可以递推得到：

$F(x) = \frac{F(\frac{x}{2})}{2} + (x个位为1) \times \frac{n}{2}$

总结

干嘛不直接抄板子，这又不是OI

模板题

洛谷P3803