快速傅里叶变换(Fast Fourier Transform)，是一种极为著名的算法，以其巧妙、高效著称。在OI领域的应用主要是多项式乘法（特殊形式是高精度乘法）。多项式乘法似乎还与组合数学有很大的联系，所以对于OI选手，是一种非常有用的必备法宝。

为什么FFT做多项式乘法更快呢？FFT原是一种信号处理算法，可以将时域数据转换为频域数据。时域乘积，频域卷积；时域卷积，频域乘积。两者互相对称。多项式乘法是两个序列的卷积，如果将其转换到频域下做乘法，再转换回来，是不是可以更快一点呢？幸运的是，这确实可以。FFT包括DFT(离散傅里叶变换)和IDFT(逆离散傅里叶变换)两部分，两者均可以用$O(N\log N)$的时间复杂度实现。

首先给出DFT的公式：${X_k} = \sum\limits_{n = 0}^{N - 1} {{x_n} \cdot {e^{ - i2\pi kn/N}}} (k = 0,1,2...N - 1)$

不要被复杂的数学描述吓到，我们来一步步分解。令${W_N} = {e^{ - i2\pi /N}}$，在N确定时，它是一个常数。那么DFT的公式可以改写为${X_k} = \sum\limits_{n = 0}^{N - 1} {{x_n} \cdot W_N^{nk}}$。观察一下，DFT实质上是一个$N \times N$的系数矩阵与长度为$N$的向量$x$的矩阵乘法，得到一个长度为$N$的向量$X$。那么根据公式就得到最朴素的$O({N^2})$算法。

公式中还有许多神奇的性质。首先普及一个常用的公式：${e^{i\theta }} = \cos \theta + i\sin \theta$，这个公式解决了虚数指数幂的运算障碍。其次根据公式可以推导得${e^{2\pi i}} = 1$。下面开始探究${W_N}$的性质：

性质1：周期性 - $W_N^{nk} = W_N^{n(N + k)}$

性质2：对称性 - $W_N^{nk} = W_N^{ - nk}$ ，证明只需要将式子展开后即可得到。

接下来是FFT的核心步骤：

$${X_k} = \sum\limits_{m = 0}^{N/2 - 1} {{x_{2m}} \cdot W_N^{2mk} + } \sum\limits_{m = 0}^{N/2 - 1} {{x_{(2m + 1)}} \cdot W_N^{(2m + 1)k}}$$

用上述性质进行进一步化简，可以得到：

$${X_k} = \sum\limits_{m = 0}^{N/2 - 1} {{x_{2m}} \cdot W_{N/2}^{mk} + } W_N^k\sum\limits_{m = 0}^{N/2 - 1} {{x_{(2m + 1)}} \cdot W_{N/2}^{mk}}$$

$${X_{N/2 + k}} = \sum\limits_{m = 0}^{N/2 - 1} {{x_{2m}} \cdot W_{N/2}^{mk} - } W_N^k\sum\limits_{m = 0}^{N/2 - 1} {{x_{(2m + 1)}} \cdot W_{N/2}^{mk}}$$

这样就把原问题等价转化为两个子问题，是FFT中体现的分治策略。最后是将频域转回时域，IDFT公式：${X_k} = \frac{1}{N}\sum\limits_{n = 0}^{N - 1} {{x_n} \cdot {e^{i2\pi kn/N}}}$

UOJ上有一道模板题。具体实现如下：

[BZOJ 2179] 高精度乘法模板~~

[BZOJ 2194] 卷积模板~~