在外网上看过很多吐槽，说中国多项式题目非常多。我才刚刚接触多项式算法，倍感恐惧，为了便于自己今后的复习，特此写篇博客。
系数表示法
您有一个 n 次多项式，或者干脆就可以把它看成一个 n 次函数 f(x)=\sum\limits_{i = 0}^{n} a_ix^i ，其中 a_i 是指的各项系数， 特别地 a_0 是常数项。
如果此时需要做多项式乘法 f(x)\times g(x) 我们直接通过暴力求解时间复杂度是 O(n^2) (在本文中将两个多项式的次数视为相同的)，因为 f(x) 和 g(x) 的每一项都要乘一遍。这个过程本质与竖式乘法没有区别，只是不需进位即可。
点值表示法
根据初中所学,一次函数需要两个不同的点确定，二次函数需要三个不同的点确定。（当然这些点的 x 坐标需要不同）显然归纳得出 n 次函数需要 n+1 个不同的点即可求出所有 n + 1 项系数。
因为我们通过待定系数法求解函数解析式的时候 n + 1 个不同的点为我们提供了 n + 1 条不同的方程，可以保证我们解出所有的 n + 1 项系数。当然，计算出来的函数并不一定正好是 n 次函数，因为某些系数可能为 0。
举个例子：如上图三次函数 f(x)=3x^3+x^2-4x+1 可以由 A(-2,-11),B(-1,1),C(0,1),D(1,1) 确定，方程如下
\begin{cases}(-2)^3a_3+(-2)^2a_2+(-2)a_1+a_0=-11 \\ (-1)^3a_3+(-1)^2a_2+(-1)a_1+a_0=3\\0^3a+0^2a_2+0a_1+a_0=1\\1^3a_3+1^2a_2+1a_1+a_0=1\end{cases}
对应地，只要我们给定 n次 多项式 A(x) 对于 n + 1 个不同的 x_i 下的取值，我们就可以确定唯一个多项式 A(x)
如果此时需要做多项式乘法 f(x)\times g(x) ，显然知道答案多项式是一个 2n + 1 次多项式，只需要分别求出 f(x) 和 g(x) 的 2n + 1 种点值，例如：
然后对应相乘得到
$\{f(0)g(0) ,f(1)g(1),...,f(2n)g(2n)\}
即是答案多项式的点值表示法！这个操作居然只需要 O(n^2) 复杂度! (等等……不跟上面暴力一样吗)
得到了点值表示法之后我们可以直接 O(n^3) 高斯消元求出来系数表示法，这不是负优化吗……
然而我们可以用一种神秘的方法使得求得点值表示法的复杂度降为 O(n \log n)
只不过这个下标不是在取 0 \sim2n-1 的整数，而是取的复数。
特殊的点值
构造一组特殊的点值，使得点值可以通过分治的方法求出。
在实数范围 \textbf{R} 中我们没有办法得到这种特殊的点值，考虑扩展值域到 \textbf{C}，即复数域。
复数介绍
复数（complex number）是形如 z=a+b\textbf{i} 的数，其中 a 称为实部，b 称为虚部，\textbf{i} 称为虚数单位，且 \textbf{i}^2 = -1。也可以就干脆把它看成一个向量(a,b)。其代数运算法则如下
设两复数 a+b\textbf{i} ，c+d\textbf{i}
-
+ 实部相加，虚部相加即可 a+c+(b+d)\textbf{i}
-
- 实部相减，虚部相减即可 a-c+(b-d)\textbf{i}
-
* 乘法满足分配律 (a+b\textbf{i})(c+d\textbf{i})=ac+(ad+bc)\textbf{i}+bd\textbf{i}^2=ac-bd+(ad+bc)\textbf{i}
其中，我们很容易可以看出 + - 运算的几何意义，即向量加减的平行四边形法则。
但对于乘法，似乎不那么容易看出。不如把复数换一个方法表示：
z_1=r_1(\cos\theta_1+\sin\theta_2\textbf{i}),z_2=r_2(\cos\theta_2+\sin\theta_2\textbf{i})
这样我们就容易推出结论了！
z_1z_2=r_1r_2(\cos\theta_1\cos\theta_2-\sin\theta_1\sin\theta_2+\sin\theta_1\cos\theta_2+\cos\theta_1\sin\theta_2)
=r_1r_2(\cos (\theta_1+\theta_2)+\sin(\theta_1+\theta_2)\textbf{i})
即模长相乘，幅角相加。
弧度制
必修四接触的一个概念，只需知道 360^{\circ}=2\pi
单位根
上文我们讲到
构造一组特殊的点值，使得系数可以通过分治的方法求出。
这组特殊的点值就是复数中的单位根的次幂。
为了方便实现，我们下文中所有提及的多项式次数 n 均默认为 2 的整数次幂。
在复平面上以原点为中心画一个半径为 1 的圆，即单位圆。以原点为起点，圆的 n 等分点为终点的向量有 n 个
我们每个向量从 \overrightarrow{OA} 到 \overrightarrow{OH} 标号为 \omega_{n}^{0},\omega_{n}^{1},..,\omega_{n}^{n-1}
其中下标表示的是对这个圆进行了几等分，上标表示的是该向量位于逆时针第几个（当然你可以理解为幂也没有问题，上面我们扯到复数/向量乘法的几何意义，你发现每个向量确实都可以用单位根的 k 次方直接得到！）。
其中 \overrightarrow{OB} 也就是 \omega_{n}^{1} 被称作单位根，也就是如果 \boldsymbol z^n=(1,0)，那么 \boldsymbol z就是单位根。
同时模仿三角函数那一套的东西，我还能给出其他的性质：
\omega_n^{x}=\omega_{n}^{x+kn},(k\in \textbf{Z})$ 这个很显然，就是向量转了 $360^{\circ}
$\omega_{n}^{x}=-\omega_{n}^{(x+\frac{n}{2})}$，显然的，转 $180^{\circ}
我们发现 \omega_{n}^{x}=(\cos \dfrac{360^{\circ}x}{n},\sin\dfrac{360^{\circ}x}{n}) 是可以直接算的，所以我们可以很方便的得到各个向量。
快速求得点值
考虑我们有一个多项式函数 A(x)，我们知道它的系数向量是 \{a_0,a_1,\cdots ,a_{n-1}\}
我们的目标是得到它的点值向量。
其中 x 取 \omega_{n}^{0},\omega_{n}^{1},\cdots,\omega_{n}^{n-1}
A(x)=a_0x^0+a_1x^1+a_2 x^2+a_3 x^3+ \cdots + a_{n-1}x ^{n-1}
设另外两个
B_1(x)=a_0x^0+a_2x^1+\cdots + a_{n-2}x^{\frac{n}{2}}
B_2(x)=a_1x^0+a_3x^1+ \cdots + a_{n-1}x^{\frac{n}{2}}
A(x)=B_1(x^2)+xB_2(x^2)
此时把 x=\omega_{n}^{k} 和 x = \omega_{n}^{k+\frac{n}{2}} 带入试试？
先带入 x=\omega_{n}^{k}。
A(\omega_{n}^{k})=B_1(\omega_{n}^{2k})+\omega_{n}^{k}B_2(\omega_{n}^{2k})
我们把 n 补全成了 2 的次幂形式。所以 \omega_{n}^{2k}=\omega_{\frac{n}{2}}^{k}
A(\omega_{n}^{k})=B_1(\omega_{\frac{n}{2}}^{k})+\omega_{n}^{k}B_2(\omega_{\frac{n}{2}}^{k})
同理把 x = \omega_{n}^{k+\frac{n}{2}} 带入，得到：
A(\omega_{n}^{k+\frac{n}{2}})=B_1(\omega_{\frac{n}{2}}^{k})-\omega_{n}^{k}B_2(\omega_{\frac{n}{2}}^{k})
发现二者式子长得除了第二个系数有正负差别以外，其他都没有区别。
意思是我们只要知道 B_1,B_2 的点值表达式，就可以用 O(n) 的时间求出 A 的点值表达式。
容易发现这是递归形式，T(n)=2T(\dfrac{n}{2})+n,T(1)=1。
复杂度 O(n \log n)。
从点值到系数
我们求得了 x 取 k 次单位根的点值，这是好的，我们直接把两个要乘起来的函数点值直接乘起来，这就是答案函数的点值表达。
但是题目一般不会让我们求点值，而是系数。
这是点值与系数的关系 c_k=\sum\limits_{i=0}^{n-1}a_i\omega_{n}^{ik}。
这是系数和点值的关系 a_i=\dfrac{1}{n}\sum\limits_{k=0}^{n-1}c_k\omega_{n}^{-ik}。
为什么？
考虑构造一个矩阵描述这个关系：
T=\begin{bmatrix}
\omega_n^{0} & \omega_n^{0} & \cdots & \omega_n^{0} \\
\omega_n^{0} & \omega_n^{1} & \cdots & \omega_n^{n-1} \\
\vdots & \vdots & \ddots & \vdots \\
\omega_n^{0} & \omega_n^{n-1} & \cdots & \omega_n^{(n-1)(n-1)}
\end{bmatrix}
则有
T
\times
\begin{bmatrix}
a_0 \\
a_1 \\
\vdots\\
a_{n-1}
\end{bmatrix}
=
\begin{bmatrix}
c_0 \\
c_1 \\
\vdots\\
c_{n-1}
\end{bmatrix}
现在已知 a 与 c 的关系，我们只要求出 T^{-1} 就可以反向求解 c 与 a 的关系。
因为有
T^{-1}
\times
\begin{bmatrix}
c_0 \\
c_1 \\
\vdots\\
c_{n-1}
\end{bmatrix}
=
\begin{bmatrix}
a_0 \\
a_1 \\
\vdots\\
a_{n-1}
\end{bmatrix}
容易发现，当 \omega_n^{k} \rightarrow \dfrac{1}{n}\omega_n^{-k} 时，这便是逆矩阵了。
所以发现我们原来在 FFT 中，单位根选择的是 \omega_n^{1} ，现在只要选择 \omega_n^{-1}=\omega_n^{n-1} 即可。
最后记得给系数 /n。
多项式求逆
已知 n-1 次多项式 F(x)，求一个多项式 G(x) 使得 F(x)G(x)\equiv 1 \pmod {x^n}。系数对 NTT 模数取模。保证 F(x) 常数项不为 0。
考虑递归构造，假如 F(x) 只有一项，我们直接求个逆元即可。
假设我们知道了一个 H(x) 使得 F(x)H(x)\equiv 1 \pmod {x^{\frac{n}{2}}}。
我们同时要求解的 G(x) 也有 F(x)G(x)\equiv 1 \pmod {x^{\frac{n}{2}}}。
\begin{aligned}
F(x)(G(x)-H(x))&\equiv 0 &\pmod {x^{\frac{n}{2}}} \\
G(x)-H(x)&\equiv 0 &\pmod {x^{\frac{n}{2}}} \\
G^2(x)+H^2(x)-2G(x)H(x)&\equiv 0 &\pmod{x^n} \\
F(x)(G^2(x)+H^2(x)-2G(x)H(x))&\equiv 0 &\pmod{x^n} \\
G(x)+F(x)H^2(x)-2H(x) &\equiv 0 &\pmod{x^n} \\
G(x)&\equiv H(x)(2-F(x)H(x)) &\pmod{x^n}
\end{aligned}
所以我们每次已经得知了一个 H(x)，可以用它算出 G(x)，并把 G(x) 作为下一轮的 H(x) 一直算下去就好了。
容易发现复杂度 T(n)=T\left(\dfrac{n}{2}\right)+n \log n，是 O(n\log n) 的。
多项式开根
已知 n-1 次多项式 F(x)，求一个多项式 G(x) 使得 G^2(x)\equiv F(x) \pmod {x^n}。系数对 NTT 模数取模。保证 F(x) 的常数项为 1。
考虑递归构造，假如 F(x) 只有常数项，我们直接求个二次剩余即可（但是他这里保证了常数项为 1 就不用算了）。
假设我们知道了一个 H(x) 使得 H^2(x) \equiv F(x) \pmod {x^{\frac{n}{2}}}。
我们同时要求解的 G(x) 也有 G^2(x)\equiv F(x) \pmod {x^{\frac{n}{2}}}。
\begin{aligned}
G(x)-H(x)&\equiv0 &\pmod {x^{\frac{n}{2}}} \\
G^2(x)+H^2(x)-2G(x)H(x) &\equiv 0 &\pmod {x^{n}} \\
2G(x)H(x) &\equiv G^2(x)+H^2(x) &\pmod {x^{n}}\\
G(x) & \equiv \dfrac{F(x)+H^2(x)}{2H(x)} &\pmod {x^n} \\
G(x) & \equiv \dfrac{1}{2}\left(\dfrac{F(x)}{H(x)}+H(x)\right) &\pmod {x^n}
\end{aligned}
所以我们每次已经得知了一个 H(x)，可以用它算出 G(x)，并把 G(x) 作为下一轮的 H(x) 一直算下去就好了。
容易发现复杂度是 O(n \log n) 的。
多项式 \ln
已知 n-1 次多项式 F(x)，求一个多项式 G(x) 使得 \ln F(x)\equiv G(x) \pmod {x^n}。系数对 NTT 模数取模。保证 F(x) 的常数项为 1。
$$
\begin{aligned}
G(x) &\equiv f(F(x)) &\pmod {x^n} \\
G'(x) &\equiv f'(F(x))F'(x) &\pmod {x^{n-1}} \\
G'(x) &\equiv \dfrac{F'(x)}{F(x)} &\pmod{x^{n-1}} \\
G(x) &\equiv \int\dfrac{F'(x)}{F(x)} &\pmod{x^n}
\end{aligned}
$$
所以我们只需要多项式求逆，多项式求导，多项式不定积分就能解决这个问题啦！
容易发现复杂度是 $O(n \log n)$ 的。
## 多项式 $\exp
已知 n-1 次多项式 F(x)，求一个多项式 G(x) 使得 F(x)\equiv \ln G(x) \pmod {x^n}。系数对 NTT 模数取模。保证 F(x) 的常数项为 0。
牛顿迭代
这是一个前置技能。
假设我们要求连续可导函数的零点，有一种方法是二分，但是它很慢。我们考虑用切线去逼近零点。具体来说我们如下操作：
已知初始近似值为 x_0，我们求得该点的切线（用点斜式表示）：
y=f'(x_0)(x-x_0)+f(x_0)
我们把它感性推广到多项式范围上去：即这样一个问题，已知 $n-1$ 次多项式 $F(x)$，请求得一个多项式 $G(x)$ 使得 $F(G(x)) \equiv 0 \pmod{x^n}$。
如果已经求得 $\bmod x^{\frac{n}{2}}$ 意义下的答案 $H(x)$ 那么有：
$$
G(x)\equiv H(x)-\dfrac{F(H(x))}{F'(H(x))} \pmod{x^n}
$$
我们接着把 $G(x)$ 作为下一轮的 $H(x)$ 就可以在 $O(\log n)$ 次以内答案了。
### 借助牛顿迭代求解 $\exp
\ln G(x)-F(x) \equiv 0 \pmod{x^n}
考虑设一个多项式 A(G(x))= \ln G(x)-F(x)。
所以我们来牛顿迭代（设 H(x) 为 \bmod x^{\frac{n}{2}}的答案）：
\begin{aligned}
G(x)&\equiv H(x)-\dfrac{\ln H(x)-F(x)}{\frac{1}{H(x)}} &\pmod{x^{n}} \\
G(x) &\equiv H(x)(1-\ln H(x) +F(x)) &\pmod {x^{n}}
\end{aligned}
代码提示：时刻注意清空数组！
容易发现复杂度是 O(n \log n) 的。
多项式快速幂
其实一切的一切都是为了这个做准备。
已知 n-1 次多项式 F(x)，求 F^k(x) \bmod x^n。系数对 NTT 模数取模。保证 F(x) 常数项为 1。
\begin{aligned}
G(x) &\equiv F^k(x) &\pmod {x^n} \\
\ln G(x) &\equiv k \ln F(x) &\pmod {x^n} \\
G(x) &\equiv e^{k \ln F(x)} &\pmod {x^n}
\end{aligned}
我们是直接把 k 乘到 \ln F(x) 的系数里所以是对 k 直接取模的（注意是对 p 取模而不是 \varphi(p)）。最终你只需要把之前的板子们一股脑往上面塞就行了。
容易发现复杂度是 O(n \log n) 的。恭喜你，经过这一套 n\log n 加持，你的常数已经大到不可想象！
多项式除法（取模）
给定 n 次多项式 F(x) 和 m 次多项式 G(x)，求出多项式 Q(x),R(x)，满足 F(x)=Q(x)G(x)+R(x)，且 Q(x) 的次数为 n-m，R(x) 次数 小于 m。运算在 NTT 模数下进行。
定义 F^r(x)=x^{DegF}F \left(\dfrac{1}{x}\right)，即把系数翻转。
\begin{aligned}
F(x)&\equiv Q(x)G(x)+R(x) &\pmod{x^{n+1}}\\
x^nF\left(\frac{1}{x}\right)&\equiv x^n\left(Q\left(\frac{1}{x}\right)G\left(\frac{1}{x}\right)+R\left(\frac{1}{x}\right)\right) &\pmod{x^{n+1}} \\
x^nF\left(\frac{1}{x}\right)&\equiv x^{n-m}Q\left(\frac{1}{x}\right)\cdot x^mG\left(\frac{1}{x}\right)+x^{n-m+1}\cdot x^{m-1}R\left(\frac{1}{x}\right) &\pmod{x^{n+1}} \\
F^r(x)&\equiv Q^r(x)G^r(x)+x^{n-m+1}R(x) &\pmod{x^{n+1}} \\
F^r(x)&\equiv Q^r(x)G^r(x) &\pmod{x^{n-m+1}} \\
Q^r(x)&\equiv F^r(x)(G^r)^{-1}(x) &\pmod{x^{n-m+1}}
\end{aligned}
由于 Q^r(x) 是 n-m 次多项式，所以模意义不会改变它的值，G(x) 保证了是 m 次多项式，所以翻转后常数项一定有逆元。求出了 Q(x) 之后就可以求 R(x) 了。
复杂度 O(n \log n)。
多项式多点求值
给定 n 次多项式 F(x)，请对于 i\in[1,m]，求出 f(a_i)。
单点求值？
如果我们要单点询问 F(x_0) 的值，我们把多项式 F(x) 写成 F(x)=(x-x_0)D(x)+R(x)，其中 D(x) 是一个 n-1 次多项式，R(x) 是一个常数函数。
那么答案就是 R(x)。R(x) 可以通过多项式除法算出。
多点求值？
单点求值这么做实在是大材小用，考虑多点求值。
把询问分成两部分，以 k=\lfloor \frac{m}{2} \rfloor 为分界，构造两个多项式 A_0(x)=\prod\limits_{i=1}^{k}(x-x_i)，A_1(x)=\prod\limits_{i=k+1}^{m}(x-x_i)。
对于两侧都可以用单点求值的方法写出：
- 左侧 F(x_i)=A_0(x_i)D_0(x)+R_0(x)=R_0(x)；
- 右侧 F(x_i)=A_1(x_i)D_1(x)+R_1(x)=R_1(x)。
那么要么 R(x) 的次数相对于 F(x) 减少了一半，要么 m 少了一半（也有可能同时，具体要看 m 的是否小于 2n），可以继续递归求。
容易发现复杂度是 O(n \log n \log(\min(n,m))) 的。
多项式多点插值
给定 n+1 个点 (x_i,F(x_i))，下标从 0 开始，还原 n 次多项式 F(x)。
拉格朗日插值可以做到 O(n^2)：
F(x)= \sum\limits_{i=0}^{n}F(x_i) \dfrac{\prod_{j \not= i }(x-x_j)}{\prod_{j\not =i}(x_i-x_j)}
右边这个式子就鬼畜，考虑重复利用——分治。令 m= \lfloor \frac{n}{2} \rfloor,y_i=\frac{F(x_i)}{\prod_{j\not=i}(x_i-x_j)}
原式子就变成了 F(x)= \sum_{i=0}^{n} y_i \prod_{j\not=i}(x-x_j)。
考虑把原式子拆成两半分治：
\begin{aligned}
F(x)&=\sum_{i=0}^{m} y_i \prod_{j=0,j\not= i}^{m}(x-x_j) \prod_{j=m+1}^{n}(x-x_j) \\
&+\sum_{i=m+1}^{n}y_i \prod_{j=m+1,j\not=i}^{n}(x-x_j) \prod_{j=0}^{m}(x-x_j)
\end{aligned}
发现两项前面一半和原式形式一模一样，于是可以分治。这一段复杂度 O(n \log n)。
两项后面的部分可以递归的时候分治 fft 求出。复杂度 O(n \log ^2n)。
现在唯一的问题是怎么求 y_i。
设多项式 P_i(x)= \frac{\prod_{j=0}^{n} (x-x_j)}{x-x_i}，那么 y_i=F(x_i)(P(x_i))^{-1}。
根据洛必达法则有 P_i(x_i)=F'(x_i)。所以可以直接算出来 P_i(x)。
至于得到 y_i 就需要多点求值。复杂度 O(n \log ^2n)。
所以算法总复杂度就是 O(n \log^2 n)，而且常数还大。
第一类斯特林数·行
求 \begin{bmatrix} n \\ i\end{bmatrix}。对 NTT 模数取模。
根据第一类斯特林数的公式 x^{\overline n}= \sum\limits_{i=0}^{n} \begin{bmatrix} n \\ i \end{bmatrix}x^n 可知，x^{\overline n} 展开后对应位置系数即为第一类斯特林数。
依然考虑倍增，已经算出了 \bmod x^{n} 的答案 F(x)，那么 \bmod x^{2n-1} 下的答案就是 G(x)=F(x)F(x+n)。
那么怎么求 F(x+n) 呢？
\begin{aligned}
设 F(x)&=\sum_{i=0}^{n}a_ix^i \\
F(x+n)&=\sum_{i=0}^{n}a_i(x+n)^i \\
&= \sum_{j=0}^{n}x^j \sum_{i=j}^{n}\dbinom{i}{j}a_i n^{i-j} \\
&= \sum_{i=0}^{n}\dfrac{x^i}{i!} \sum_{j=i}^{n}j!a_j \times \dfrac{n^{j-i}}{(j-i)!}
\end{aligned}
减法卷积的形式。可以 O(n \log n) 计算。再花费 O(n \log n) 把 F(x) 和 F(x+n) 卷起来。
总复杂度 O(n \log n)。
第二类斯特林数·行
求 \begin{Bmatrix} n \\i\end{Bmatrix}。对 NTT 模数取模。
总复杂度 $O(n \log n)$。