~~重振卡门雄风，吾辈义不容辞！~~

正文

一，快速傅里叶变换（FFT）

前置芝士：

概念

时域：以时间为自变量，函数值为因变量的平面。
频域：以频率为自变量，振幅为因变量的坐标系。
多项式的系数表示法：\(A(x)=\sum_{k=0}^{n-1} a_k\times x^k\)
多项式的点值表示法：用 \(n\) 个点描述一个 \(n-1\) 次的多项式。

复数

\(n\) 次单位复数根：\(\omega^n=1\)，\(\omega\) 是复数。
用三角函数理解：\(e^{ix}=\cos(x)+i\times\sin(x)\)
定义 \(\omega_n=e^{\frac{2\pi i}{n}}\) 主 \(n\) 次单位根。
\(\omega_n^k=e^{\frac{2\pi ik}{n}}\)
引理：

消去引理：当 \(n\ge0,k\ge0,d\ge0\)，\(\omega_{dk}^{dk}=\omega_n^k\)，\((e^{\frac{2\pi i}{dn}})^{dk}=(e^{\frac{2\pi i}{n}})^k\)
折半引理：若 \(n>0\) 且 \(n\%2=0\)，则 \(n\) 个 \(n\) 次单位复数根的平方的集合就是 \(\frac{n}{2}\) 个 \(\frac{n}{2}\) 次复数根的集合。也就是说，\((\omega_n^k)^2=\omega _\frac{n}{2}^k\)
求和引理：\(\sum_{j=0}^{n-1}(\omega_n^k)^j=0\)，其中 \(n\ge1\)，\(k\) 不整除 \(n\)，\(k\ge0\)。
对于 \(j,k=0,1,2,...,n-1\)，\(V_n^{-1}(V 是系数矩阵)\) 在 \((j,k)\) 的值是 \(\frac{\omega_n^{-kj}}{n}\)
\(a_j=\frac{1}{n}\sum_{k=0}^{n-1}y_k\omega_n^{-kj}\)

定义 \(y_k=A(\omega_n^k)=\sum_{i=0}^{n-1} a_i\times\omega_n^{ki}\)
假设 \(n\) 是偶数。
\(A(x)=a_0+a_1x+a_2x^2+...+a_{n-1}x^{n-1}\)
\(A_0(x)=a_0+a_2x^2+a_4x^4+...+a_{n-2}x^{n-2}\)
\(A_1(x)=a_1x+a_3x^3+a_5x^5+...+a_{n-1}x^{n-1}\)
则 \(A(x)=A_0(x^2)+A_1(x^2)\times x\)

流程：

\(A(x) (a_0,a_1,...,a_{n-1}),B(x) (b_0,b_1,...,b_{n-1})\)
通过 FFT
\(A(x_0)\times B(x_0),A(x_1)\times B(x_1)...A(x_{2n-2})\times B(x_{2n-2})\)
通过点值乘法
\(C(x_0),...,C(x_{2n-1})\)
通过 FFT 插值
\(C(x)={C_0,C_1,...,C_{2n-2}}\)