快速傅立叶变换 FFT
对于两个多项式
$$A(x)=\sum_{i=0}^{N-1}a_ix^i$$
$$B(x)=\sum_{i=0}^{N-1}b_ix^i$$
FFT可以在$O(nlgn)$的时间内求出
$$C(x)=A(x)*B(x)=\sum_{i=0}^{2(N-1)}c_ix^i$$
其中$c_i=\sum_{j=0}^ia_jb_{i-j}$
前置知识
在复数域下，方程$x^n=1$有$n$个解$\omega_N^i,(i=1\dots N)$
其中
$$\omega_N^i=(\cos\frac{2\pi i}{N}, \sin\frac{2\pi i}{N})$$
可以看作是平面直角坐标系中单位圆上间距相等的$N$个点
然后可以自己去学习一下复数)一下qwq
假如把复数用极坐标表示
$z=r(\cos \varphi+i\sin \varphi)$
那么复数的乘法就是模长($r$)相乘，幅角($\varphi$)相加
单位根有如下性质：
$$\omega_N^i\omega_N^j=\omega_N^{i+j}$$
$$\omega_N^i=\omega_N^{N+i}$$
$$\omega_N^{\frac{N}{2}}=-1$$
$$\omega_N^i=\omega_{cN}^{ci}$$
DFT
我们尝试将$N$下的单位根代入多项式得到$N$个值
也就是
$$F:{a_0,a_1,\dots a_{N-1}} \to {A(\omega_0),A(\omega_1),\dots A(\omega_{N-1})}$$
显然，可以在$A,B$中补$0$使得$N=2^k(k\in \mathbb{N})$
考虑分治
对于$0\leq i < \frac{N}{2}$
有
$$
\begin{aligned}
A_i&=\sum_{j=0}^{N-1}a_j\omega_N^{ij}
\
A_{i+\frac{N}{2}}&=\sum_{j=0}^{N-1}a_j\omega_N^{(i+\frac{N}{2})j}=\sum_{j=0}^{N-1}(-1)^ja_j\omega_N^{ij}
\end{aligned}
$$
将$\sum$中的奇偶项分开来
$$
\begin{aligned}
A_i&=\sum_{j=0}^{\frac{N}{2}-1}a_{2j}\omega_{\frac{N}{2}}^{ij}+\omega_N^i\sum_{j=0}^{\frac{N}{2}-1}a_{2j+1}\omega_{\frac{N}{2}}^{ij}
\
A_{i+\frac{N}{2}}&=\sum_{j=0}^{\frac{N}{2}-1}a_{2j}\omega_{\frac{N}{2}}^{ij}-\omega_N^i\sum_{j=0}^{\frac{N}{2}-1}a_{2j+1}\omega_{\frac{N}{2}}^{ij}
\end{aligned}
$$
非常奇妙是不是？这样就可以分治下去啦
IDFT
与DFT类似
只不过将DFT中的每个$\omega$都变成$\omega^{-1}$，然后最后每个$A_i$都除以$N$
代入进去显然可以发现是对的。
如果要严格说明是唯一的话就要用线性代数中的Vandermonde矩阵了。。
这里就不写了，感兴趣的可以去了解一下，《算法导论》里讲的也挺详细的
例题
来自衲姐NiroBC的例题（Orz）
给一个$N$位的$B$进制数$A$，将它转为十进制。($N,B\leq 10^5$)
考虑分治
对于$N$位的$B$进制数，
设$M=2^k\leq \frac{N}{2}$
假如我们已经求出了$\sum_{i=0}^{M-1}A_iB^i$的十进制数以及$\sum_{i=0}^{N-M-1}A_{i+M}B^i$的十进制数
那么就可以用FFT将$\sum_{i=0}^{N-M-1}A_{i+M}B^i$乘上$B^M$
其中$B^M$的十进制数也可以用FFT预处理
时间复杂度为$O(nlg^2n)$
快速数论变换 NTT
NTT与FFT大体上十分相似
主要是因为FFT涉及许多实数运算，因此很容易丢精
当需要对所求的多项式对$M$取模时，NTT就是一个非常好的选择
欧拉定理)：
若$n,a$为正整数，且$n,a$互素（即$\gcd(a,n)=1$），则
$$a^{\varphi(n)}\equiv 1 \quad (mod\; n)$$
NTT一般用于$M$是质数的情况，因此在这里费马小定理：
费马小定理：
假如$a$是一个整数，$p$是一个质数
$$a^{p-1}\equiv 1 \quad (mod\; p)$$
原根$G$，满足集合${G^0, G^1, G^2, \cdots, G^{\varphi(M) - 1}}$中含有了所有与$M$互质的数。
若$M$可以表示成$2^k*t+1$， 其中$t$是奇数
那么对于小于$2^k$的$N$，$G^{\frac{M-1}{N}}$都可以作为单位元$w$，其他就和FFT没什么区别了