快速傅里叶变换
0 记号
- \(\exp(x)=e^x\)。
1 复数 (Complex)
1.1 三种形式
-
代数形式：\(z=a+bi\)，其中 \(a,b\in\mathbb R\)。
-
三角形式：\(z=r(\cos\theta+i\sin\theta)\)，其中 \(r=\sqrt{a^2+b^2}\)（\(a,b\) 是在代数形式中定义的）。
-
指数形式：\(z=r\cdot e^{i\theta}\)。
根据 欧拉公式：
\[e^{ix}=\cos x+i\sin x,x\in\mathbb C \]令 \(x=\theta\)，再带入三角形式中，即可得指数形式。
1.2 单位根 (unit root)
对于方程 \(x^n=1\)，在复数意义下，她有 \(n\) 个解，我们称这 \(n\) 个解都是 单位根 (unit root)。
定义 \(\boxed{\omega_n=\exp\frac{2\pi i}n}\)，则这 \(n\) 个单位根可以表示为 $ {\omega_n^k\mid k=0,1\cdots,n-1} $。
在复平面中，\(n\) 次单位根把单位圆 \(n\) 等分。
2 快速傅里叶变换 (Fast Fourier Transform)
FFT 可以在 \(O(n\log n)\) 的时间复杂度内，计算多项式乘法，而不是暴力的 \(O(n^2)\)。
2.1 定义
对于一个多项式 \(f(x)\)，定义快速傅里叶变换为：
\[\boxed{\mathcal F(f(x))=\left(f(1),f(\omega_n),\dots,f(\omega_n^n)\right)} \]快速傅里叶变化实际上可以理解为一种「从一个多项式到一个 \(n\) 维向量的映射/变化规则」（？
2.2 求解
2.2.1 引入
一种思想：
考虑如何计算 \(\sum\limits_{i=0}^na_ix^i\)。
一般的方法是，枚举 \(i\)，然后维护 \(x^i\) 的值 \(k\)，再将 \(a_i\) 与 \(k\) 相乘并累加。精细统计的话，这样应该需要 \(2n\) 次乘法。
另一种办法是：
\[\begin{aligned}\sum\limits_{i=0}^na_ix^i &=a_0+a_1x+\cdots+a_nx^n\\ &=a_0+x\left(a_1+x\left(a_2+\cdots xa_n\right)\right)&\text{【就是每次都把后面一部分提一个 }x\text{ 出来】} \end{aligned}\]如果是这样计算，总共只需要 \(n\) 次计算。
借用上述思想，对于一个多项式 \(f(x)\)，我们可以做如下的变换。