二刷。写一点不那么宝宝的内容。
FFT
我们希望快速计算加乘卷积。FFT 是一种变换，使得卷积能转化成点值乘积，从而线性计算。大多数变换通常都是这个思路。
卷积在多项式中的意义，就是多项式乘法。
然后 FFT 在多项式中的意义就是，求出 \(\omega_n^0, \omega_n^1, \dots,\omega_n^{n-1}\) 处的点值。逆变换就是反过来。
- 为什么选择单位根？
这个问题。讲道理单从变换的角度，选择任意 \(n\) 个“线性无关”的点值显然都是可行的。但是你不会算多项式多点求值，你也不会快速插值。寄。
单位根具有良好的周期性，以及良好的分治结构。
关于证明，假设我们取出了 \(x^0\sim x^{n-1}\) 这些点值。
\[\begin{aligned}
FFT(A)_i \times FFT(B)_i&=(\sum_{j=0}^{n-1}A_jx_i^j)(\sum_{j=0}^{n-1}B_jx_i^j)\\
&=\sum_{t=0}^{2n-2}\sum_{j+k=t}A_jB_k \cdot x_i^j\cdot x_i^k\\
&=\sum_{t=0}^{2n-2}C_tx_i^t\\
&=FFT(C)_i
\end{aligned}
\]