一、
给定多项式：
A(x)=∑i=0n−1aixiA(x)=\sum_{i=0}^{n-1}a_ix^i A(x)=i=0∑n−1 ai xi
目标：快速计算：
A(x0),A(x1),…,A(xn−1)A(x_0),A(x_1),\dots,A(x_{n-1}) A(x0 ),A(x1 ),…,A(xn−1 )
暴力复杂度：
O(n2)O(n^2) O(n2)
FFT 目标：
O(nlogn)O(n\log n) O(nlogn)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二、单位根）
1. N 次单位根定义
ωn=e2πi/n\omega_n=e^{2\pi i/n} ωn =e2πi/n
性质：
ωnn=1\omega_n^n=1 ωnn =1
2 基本引理
折半引理
ω2n2k=ωnk\omega_{2n}^{2k}=\omega_n^k ω2n2k =ωnk
消去引理
ωnk+n/2=−ωnk\omega_n^{k+n/2}=-\omega_n^k ωnk+n/2 =−ωnk
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三、多项式拆分
将 A(x) 按奇偶拆分：
A(x)=a0+a1x+⋯+an−1xn−1=(a0+a2x2+… )+(a1x+a3x3+… )=Ae(x2)+xAo(x2)\begin{aligned} A(x)&=a_0+a_1x+\dots+a_{n-1}x^{n-1}\\ &=(a_0+a_2x^2+\dots)+(a_1x+a_3x^3+\dots)\\ &=A_e(x^2)+xA_o(x^2) \end{aligned} A(x) =a0 +a1 x+⋯+an−1 xn−1=(a0 +a2 x2+…)+(a1 x+a3 x3+…)=Ae (x2)+xAo (x2)
其中：
Ae(x)=a0+a2x+…Ao(x)=a1+a3x+…\begin{aligned} A_e(x)&=a_0+a_2x+\dots\\ A_o(x)&=a_1+a_3x+\dots \end{aligned} Ae (x)Ao (x) =a0 +a2 x+…=a1 +a3 x+…
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
四、DFT 递归
在单位根处求值：
yk=A(ωnk)y_k=A(\omega_n^k) yk =A(ωnk )
代入奇偶分解：
A(ωnk)=Ae(ωn2k)+ωnkAo(ωn2k)A(\omega_n^k)=A_e(\omega_n^{2k})+\omega_n^kA_o(\omega_n^{2k}) A(ωnk )=Ae (ωn2k )+ωnk Ao (ωn2k )
由折半引理：
ωn2k=ωn/2k\omega_n^{2k}=\omega_{n/2}^k ωn2k =ωn/2k
于是：
A(ωnk)=Ae(ωn/2k)+ωnkAo(ωn/2k)A(\omega_n^k)=A_e(\omega_{n/2}^k)+\omega_n^kA_o(\omega_{n/2}^k) A(ωnk )=Ae (ωn/2k )+ωnk Ao (ωn/2k )
同理：
A(ωnk+n/2)=Ae(ωn/2k)−ωnkAo(ωn/2k)A(\omega_n^{k+n/2})=A_e(\omega_{n/2}^k)-\omega_n^kA_o(\omega_{n/2}^k) A(ωnk+n/2 )=Ae (ωn/2k )−ωnk Ao (ωn/2k )
一对结果，只用算一半
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
五、递归 FFT 伪代码
复杂度：
T(n)=2T(n/2)+O(n)⇒O(nlogn)T(n)=2T(n/2)+O(n)\Rightarrow O(n\log n) T(n)=2T(n/2)+O(n)⇒O(nlogn)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
六、蝴蝶操作
核心计算单元：
{u=yev=ωnkyo⇒{yk=u+vyk+n/2=u−v\begin{cases} u=y_e\\ v=\omega_n^k y_o \end{cases} \Rightarrow \begin{cases} y_k=u+v\\ y_{k+n/2}=u-v \end{cases} {u=ye v=ωnk yo ⇒{yk =u+vyk+n/2 =u−v
这就是蝴蝶结构的来源。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
七、迭代 FFT
1. 递归的问题
* 函数调用开销
* 内存访问不连续
2. 迭代思想
* 自底向上合并
* 每一层处理长度为 len 的区间
3. 位逆序置换（RADER）
索引二进制反转后排序：
目的：让递归叶子顺序对齐~
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
八、迭代 FFT の流程
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
九、逆 FFT（IFFT）
DFT 矩阵：
Fjk=ωnjkF_{jk}=\omega_n^{jk} Fjk =ωnjk
逆变换：
F−1=1nF‾F^{-1}=\frac{1}{n}\overline{F} F−1=n1 F
实现方法：
把 ω_n 换成 ω_n^{-1}
最后整体除以 n
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十、卷积
多项式乘法：
c=a∗bc=a*b c=a∗b
步骤：
FFT(a)→AFFT(b)→BCk=AkBkIFFT(C)→c\begin{aligned} &\text{FFT}(a)\rightarrow A\\ &\text{FFT}(b)\rightarrow B\\ &C_k=A_kB_k\\ &\text{IFFT}(C)\rightarrow c \end{aligned} FFT(a)→AFFT(b)→BCk =Ak Bk IFFT(C)→c
复杂度：
O(nlogn)O(n\log n) O(nlogn)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十一、边界条件
项目 要求 n 2 的幂 模运算 NTT 精度 double / long double 长度 ≥ deg(a)+deg(b)+1
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十二、速记公式卡片
ωn=e2πi/nω2n2k=ωnkA(ωnk)=Ae(ωn/2k)+ωnkAo(ωn/2k)蝴蝶:yk=u+v, yk+n/2=u−vIFFT:ωn→ωn−1, /n\boxed{ \begin{aligned} &\omega_n=e^{2\pi i/n}\\ &\omega_{2n}^{2k}=\omega_n^k\\ &A(\omega_n^k)=A_e(\omega_{n/2}^k)+\omega_n^kA_o(\omega_{n/2}^k)\\ &\text{蝴蝶}:y_k=u+v,\ y_{k+n/2}=u-v\\ &\text{IFFT}:
\omega_n\rightarrow\omega_n^{-1},\ /n \end{aligned} } ωn =e2πi/nω2n2k =ωnk A(ωnk )=Ae (ωn/2k )+ωnk Ao (ωn/2k )蝴蝶:yk =u+v, yk+n/2 =u−vIFFT:ωn →ωn−1 , /n
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
本人除了爱写一些暴力算法就没啥好些的
