• 多项式乘法（快速傅里叶变换）

两个多项式$A(x),B(x),$求$C(x)=A(x)*B(x)$

简单的说，我们可以考虑先在$O(nlogn)$时间内把系数表示的$A(x),B(x)$转成点值表达，再用$O(n)$时间计算出$C(x)$的点值表达，最后用$O(nlogn)$时间内把$C(x)$转换为系数表达。

系数表示转点值表示称为$DFT$，点值表示转系数表示称为$IDFT$

前置技能：单位根

满足$x^n=1$的复数$n$有个，分别为$\omega^k_n=e^{i\frac{2k\pi}{n}}$，其中称$\omega^1_n$位主$n$次单位根.

单位根有些很好的性质：

1. $\omega^i_n=\omega^{i-1}_n*\omega^1_n$（复平面旋转）
2. $\omega^j_n\omega^k_n=\omega^{j+k}_n=\omega^{j+k\mod n}_n$（群的性质）
3. $\omega^{dk}_{dn}=\omega^{k}_n$（互质性质）

（为了方便进行$DFT$和$IDFT$，下文中的$n$均是不小于多项式次数界的最小$2$的幂次）

$DFT$：

系数表示转点值表示中点值的选取是有讲究的。

先记$A(x)=\sum_{i=0}^{n-1}a_ix^i.$计算$A(x)$在n次单位根处的取值。

定义新多项式

$$A^{[0]}(x)=a_0+a_2x+a_4x^2+\cdots+a_{n-2}x^{\frac{n}{2}-1}$$

$$A^{[1]}(x)=a_1+a_3x+\cdots+a_{n-1}x^{\frac{n}{2}-1}$$

开心地发现：

$A^{[0]}(x),A^{[1]}(x)$在$A(\omega^0_n)^2,\cdots,(\omega^{n-1}_n)^2$的值.

次数减半，递归硬艹。

$IDFT$：

$IDFT$实质上就是一个矩阵乘法

$$\left(\begin{array}{ccccc}\omega_{n}^{0} & \omega_{n}^{0} & \omega_{n}^{0} & ... & \omega_{n}^{0} \\\omega_{n}^{0} & \omega_{n}^{1} & \omega_{n}^{2} & ... & \omega_{n}^{n} \\\omega_{n}^{0} & \omega_{n}^{2} & \omega_{n}^{4} & ... & \omega_{n}^{2n} \\...            & ...            & ...            & ... & ...            \\\omega_{n}^{0} & \omega_{n}^{n-1} & \omega_{n}^{2n-2} & ... & \omega_{n}^{n^2-n}\end{array}\right)*\left(\begin{array}{c}a_0 \\a_1 \\a_2 \\... \\a_{n-1}\end{array}\right)=\left(\begin{array}{c}b_0 \\b_1 \\b_2 \\... \\b_{n-1} \\\end{array}\right)$$

关键是找到左边矩阵的逆矩阵。可以构造出来：每个元素取共轭复数，再除以$n$。正确性易证。

到此我们已经可以写出一个常数较大的递归FFT了。

蝴蝶变换

观察到我们的分治是将奇偶分类，即对于每一层我取这层对应位数的0放在一起，1放在一起。

引入$Cooley-Tukey$算法的图（点击放大）：

可以看到，我们每次取对应的两个元素，进行一次“蝴蝶变换”，即完成快速傅里叶变换章节中的对两个元素进行的操作。

快速数论变换（$NTT$）

复数计算常数大，误差大，$NTT$可以做到多项式乘法的过程中取模。

当模数十分特殊时可以用数论变换加速，基于一个极强的等价：

$$g^{\frac{P-1}{m}}\equiv \omega_{m} \pmod{P}$$

其中$g$是$P$的原根。

条件是$2^k|P-1$，其中$2^k>n.$

• 多项式求逆

多项式$A(x)$，求多项式$B(x)$，满足$$A(x)*B(x) \equiv 1 \pmod{x^n}$$

这里我们将使用一种倍增的思想来完成。
首先，当$n = 1 $时， $ B[0] = A[0]^{-1} $.
假如我们已经求出了在模 $ x^{\lceil \frac{t}{2} \rceil}$意义下的答案 $ B_0(x)$，要求在 $ x^t $意义下的答案。
那么：

$$\begin{eqnarray}A(x)*B_0(x) & \equiv & 1 \pmod{x^{\lceil \frac{t}{2} \rceil}} \\A(x)*B(x) & \equiv & 1 \pmod{x^{\lceil \frac{t}{2} \rceil}} \end{eqnarray}$$

由于 $A(x)$逆元$B_0(x)$存在，故得：

$$B(x)-B_0(x) \equiv 0 \pmod{x^{\lceil \frac{t}{2} \rceil}}$$

那么我们将等式各部分平方，展开后得：

$$B^2(x)-2*B(x)*B_0(x)+B_0^2(x) \equiv 0 \pmod{ x^t }$$

两边同乘$A(x)$，利用逆元的性质移项便可得：

$$B(x) \equiv B_0(x)*(2-A(x)*B_0(x)) \pmod{ x^t }$$

上式便可在$O(t \log t)$时间内求出了。
由于每次是倍增的，所以总复杂度可得为 $ O(n \log n) $.

• 多项式除法