普通卷积
对于两个函数 \(f(x),g(x)\)，定义其卷积为
\[
(f*g)(x)=\sum_{i=0}^{n-1}{f(i)g(x-i)}
\]
傅里叶变换
此处我们只讨论离散的傅里叶变换。
数学上，\(n\) 次单位根（\(n\in \N^*\)）是 \(n\) 次幂为 \(1\) 的复数。\(n\) 次单位根有 \(n\) 个，分别是
\[
w_n^k=e^{i\frac{2k\pi}{n}}
\]
单位根在 FFT 中发挥很大的作用。
对于序列 \(\{x_n\}_0^{N-1}\)，定义其傅里叶变换为：
\[
\hat{x}_k=\sum_{n=0}^{N-1}{x_ne^{-i\frac{2k\pi}{N}n}}
\]
相应的，有逆傅里叶变换（IDFT）：
\[
x_n=\frac{1}{N}\sum_{k=0}^{N-1}{\hat{x}_ke^{i\frac{2n\pi}{N}k}}
\]
IDFT 能得到原序列的证明
给 DFT 得到的序列再进行一次相似的变换，就能得到原序列，这个结论不是很显然。我们现在着手证明这一结论。
将 DFT 的定义代入 IDFT 的定义：
\[
\begin{align*}
x_n&=\frac{1}{N}\sum_{k=0}^{N-1}{(\sum_{n'=0}^{N-1}{x_{n'}e^{-i\frac{2k\pi}{N}n'}})e^{i\frac{2k\pi}{N}n}}\\
&=\frac{1}{N}\sum_{k=0}^{N-1}{\sum_{n'=0}^{N-1}{x_{n'}e^{i\frac{2k\pi}{N}(n-n')}}}\\
\end{align*}
\]
容易发现，\(n\ne n'\) 时，由于系数 \(k\) 的存在，\(e^{i\frac{2k\pi}{N}(n-n')}\) 会成为复平面单位圆上的一些点，其总和一定等于 \(0\)；而 \(n=n'\) 时，\(e^{i\frac{2k\pi}{N}(n-n')}\) 恒等于 \(1\)。
因此，对于下标 \(n\)，只有 \(x_n\) 会产生贡献；又因为外层 \(\sum\) 一共求和了 \(N\) 次，因此要加上归一化系数 \(\frac{1}{N}\)。
DFT 有很好的性质：两个序列 DFT 的乘积等于它们卷积的 DFT。这使得我们通过 DFT 可以解决很多卷积问题。
证明
对于长度为 \(n\) 的两个序列 \(a\) 和 \(b\)，求证：对于其卷积 \(\{c_n\}_0^{2N-2}\)
\[
c_n=\sum_{k=\max(0,n-N+1)}^{n}{a_kb_{n-k}}
\]
满足
\[
\sum_{n=0}^{2N-2}{c_ne^{-i\frac{2k\pi}{N}n}}=
(\sum_{n=0}^{N-1}{a_ne^{-i\frac{2k\pi}{N}n}})
(\sum_{n=0}^{N-1}{b_ne^{-i\frac{2k\pi}{N}n}})
\]
证明：
即证
\[
\sum_{n=0}^{2N-2}\sum_{k=\max(0,n-N+1)}^{n}{a_kb_{n-k}}{e^{-i\frac{2k\pi}{N}n}}=
\sum_{n_1=0}^{N-1}\sum_{n_2=0}^{N-1}{a_{n_1}b_{n_2}e^{-i\frac{2k\pi}{N}(n_1+n_2)}}
\]
使用换元法，令 \(n=n_1+n_2\)，发现原式显然成立。
FFT：更快的 DFT
暴力 DFT 显然是 \(O(n^2)\) 的。我们考虑优化。
容易发现，DFT 等价于给一个多项式函数在不同单位根处求值。并且此函数的系数等于序列中对应的元素。
如果直接暴力计算多项式，时间复杂度会达到 \(O(n^2)\)。但我们可以通过分治的方法将时间复杂度降低到 \(O(n\log n)\)。
设多项式函数 \(f(x)=a_0+a_1x+a_2x^2+\cdots a_{n-1}x^{n-1}\)。
为了方便计算，我们将 \(n\) 取为 \(2\) 的整数次幂，高次系数补 \(0\)。
将奇数次项和偶数次项分离，得到：
\[
f(x)=G(x^2)+xH(x^2)
\]
其中
\[
G(x)=a_0+a_2x+a_4x^2+\cdots+a_{n-2}x^{\frac{n-2}{2}}\\
H(x)=a_1+a_3x+a_5x^2+\cdots+a_{n-1}x^{\frac{n-2}{2}}
\]
代入单位根 \(w_n^k\)：
\[
f(w_n^k)=G(w_n^{2k})+w_n^kH(w_n^{2k})
\]
根据单位根的性质，得到：
\[
f(w_n^k)=G(w_{\frac{n}{2}}^k)+w_n^kH(w_{\frac{n}{2}}^k)\]
\[
f(w_n^{k+\frac{n}{2}})=G(w_{\frac{n}{2}}^k)-w_n^kH(w_{\frac{n}{2}}^k)
\]
这两个式子说明，若已经知道 \(G(x)\) 和 \(H(x)\) 的 DFT，即可在 \(O(n)\) 的时间复杂度内得到 \(f(x)\) 的 DFT。这样问题的规模就被缩小了一半。
时间复杂度分析
设 FFT 的时间复杂度为 \(T(n)\)，有如下式子成立：
\[
T(n)=2T(\frac{n}{2})+O(n)
\]
根据主定理，\(T(n)=O(n\log n)\)。
NTT：没有误差的 FFT
正在学习...