快速傅里叶离散变换FFT （更新中）

声明：参考了 $yyc$ 的 blog 和 PPT (from smwc) ，以及 $wzr$ 的 blog 。

Part 1 多项式

• 定义：对于有限数列 $A_0$~${}_n$ ，形如 $A(x)=a_0+a_{1}x+a_2{x}^2+...+a_n{x}^n$ （即 $A(x)={\sum }_{i=0}^n{A}_i{x}^i$） 的函数称为多项式。记 $A(x)$ 的 $x^n$ 项系数为 $[x^n]A(x)$ ，简写为 $A[n]$ 。
• 运算：
  • 加法：$C(x)=A(x)+B(x)={\sum }_{i=0}^n(A_i+B_i)x^i$
  • 减法：$C(x)=A(x)-B(x)={\sum }_{i=0}^n(A_i-B_i)x^i$
  • 乘法：$C(x)=A(x)\times B(x)={\sum }_{i=0}^n{\sum }_{j=0}^m{A}_i{B}_j{x}^{i+j}$
• 卷积：某二元运算 $\oplus$ 的定义域和值域均为 $\mathbb{N}$ ，数列 $A,B$ 的 $\oplus$卷积 为一个新数列 $C$ ，有 $C[k]={\sum }_{i\oplus j=k}A[i]B[j]$ （$\oplus$ 可以代表任意运算符）。容易发现，多项式乘法就是“加法卷积”。

---

Part 2 FFT概论

对于两个多项式的乘法，有简单粗暴的 $O(n^2)$ 级别方法。但这只适用于少部分题目，于是某个天才就发明的一种新方法，叫 Fast Fourier Transformation（FFT）。利用卷积思想，化乘为加，快速计算多项式乘法，只需 $O(nlogn)$ 。

---

Part 3 点值与插值

• 点值：将多项式 $A(x)$ 视为函数，对于常数 $t_0$ ，$A(t_0)={\sum }_{i=0}^{+\infty }A[i]t_0^i$ 为 $A(x)$ 在 $t_0$ 处的点值。
  • 作用：已知 $A(x),B(x),C(x)$，可以快速判断 $C(x)=A(x)B(x)$ ；
  • 核心：通过选择具体的常数，将复杂的多项式乘法转换成数的乘法，提升效率。
• 插值：已知 $A(x)$ 的若干点，求 $A(x)$ 的系数序列。

将上面两种表示法组合起来，就有一个 “求值-插值法” ,得到多项式乘法一个新想法。即，把系数表达转换为点值表达 (DFT) -> 点值表达相乘 -> 把点值表达转换为系数表达 (IDFT)。
这就是 $FFT$ 的思路：

1. 选择一个足够大的 $n$，选定 $n$ 个不同的数 $x_1,x_2,x_3,...,x_n$ ；
2. 求出点值 $A(x_1),A(x_2),...,A(x_n)$ 和 $B_{(}{x}_1),B(x_2),...,B(x_n)$ ；
3. 根据 $C(x_i)=A(x_i)B(x_i)$ 得到 $C(x_1),C(x_2),...,C(x_n)$ :
4. 插值求出 $C(x)$ 的系数；

---

Part 4 复数，单位根

考虑如何做 FFT 的第一步（即选择 $n$ 个不同的数），一般直觉会选正整数等一些熟悉的数，但这没什么性质（加速不了多项式乘法）。于是单位根就登场了……

• 复数：令虚单位 $i$ 满足 $i^2=-1$，形如 $a+bi$ ($a,b\in \mathbb{R}$) 的数称为复数。
  将复数 $z=a+bi$ 看作平面直角坐标系中的点 $P(a,b)$ ，原点 $O(0,0)$，称表示复数的平面直角坐标系为复平面，$r=|OP|$ 为 $z$ 的模长，射线$OP$ 与 $x$轴正半轴的夹角 $\theta$ 为 $z$ 的辐角。有 $z=r(cos\theta +i$‌ $sin\theta )$ 。
  • 复数加法：$(a+bi)+(c+di)=(a+c)+(b+d)i$
  • 复数减法：$(a+bi)-(c+di)=(a-c)+(b-d)i$
  • 复数乘法：$(a+bi)\times (c+di)=ac-bd+(ad+bc)i$
  • 复数除法：$(a+bi)$ ‍ $/$ ‍ $(c+di)=\frac{ac+bd}{c^2+d^2}+\frac{bc-ad}{c^2+d^2}i$
  • 复数的共轭：$a+bi$ 的共轭为 $a-bi$
• 单位根：$n$ 次本原单位根记为 ${\omega }^n$ ($n\in \mathbb{N}$)，单位根为复数，满足 ${\omega }^n=1$ ，且 ${\omega }^0,{\omega }^1,{\omega }^2,...,{\omega }^{n-1}$ 互不相同。
  引入 单位圆（圆心在原点且半径为 $1$ 的圆）：
  记第 $n$ 个 $n$ 次单位根为 ${\omega }_n^{n-1}。$有 ${\omega }_n^k=k(cos\frac{2\pi }{n}+i$‌ $sin\frac{2\pi }{n})$ 。
  ${\omega }_n$ 是模长为 $1$ ，圆上的点所表示的复数模长都为 $1$ ，所以单位根一定在单位圆上。又有 ${\omega }_n$ 的辐角为 $\frac{2\pi }{n}$ (即 $\frac{1}{n}$ 圆周)，乘一次 ${\omega }_n$ 相当于绕原点逆时针旋转 $\frac{1}{n}$ 圆周，乘 $n$ 次恰好转完一圈回到原地，满足 “${\omega }^n=1$ ，且 ${\omega }^0,{\omega }^1,{\omega }^2,...,{\omega }^{n-1}$ 互不相同” 这一条件。
  
• 单位根的一些性质：
  1. ${\omega }_n^0=1$
  2. ${\omega }_n^k=({\omega }_n^1{)}^k$
  3. ${\omega }_n^i\times {\omega }_n^j=({\omega }_n^1{)}^i\times ({\omega }_n^1{)}^j={\omega }_n^{i+j}$
  4. ${\omega }_n^{-k}={\omega }_n^{n-k}$
  5. ${\omega }_{2n}^{2k}={\omega }_n^k={\omega }_{pn}^{pk}$
  6. ${\omega }_n^{(k+n/2)}=-{\omega }_n^k$

Part 5