　引言

众所周知，多项式在OI中是一项很实用的技能，现在将多项式的有关知识总结一下。

前置技能

认识汉字以及常用的基本词汇，如果此项有问题，请移步这里
基本数学知识（四则运算，多项式的概念等），如果此项有问题，请移步这里
一些高中数学知识和高数知识（泰勒展开等），如果此项有问题，请自行学习
FFT、NTT等多项式基本算法

符号及约定

若不做特殊说明，$n$代指多项式的长度（次数+1）
$[x^i]f(x)$表示多项式$f(x)$的$i$次项系数。
若不做特殊说明，本文的运算均在$998244353$或其他费马素数的剩余系下的意义进行。

多项式加减法

直接$\mathcal{O}(n)$。

多项式乘法

暴力卷积 $\mathcal{O}(n^2)$。

使用NTT可加速至$\mathcal{O}(n \log n)$

多项式求逆

首先，求逆必须要在$\bmod x^k$的意义下进行。

现在假设我们已知$n$次多项式$f(x)$，现在要求$g(x)$使得$ f(x) \times g(x) \equiv1 \pmod {x^{n+1}} $。

我们使用倍增算法。

假设已知$g_0(x)$使得$f(x) \times g_0(x) \equiv 1 \pmod{x^{\frac{n}{2}}}$，

现在要求$g(x)$使得$f(x) \times g(x) \equiv 1 \pmod{x^n}$。

$\begin{aligned} \because f(x) \times g_0(x) & \equiv 1 & \pmod{x^{\frac{n}{2}}} \\ f(x) \times g(x) & \equiv 1 & \pmod{x^{\frac{n}{2}}} \\ \therefore g(x)-g_0(x) & \equiv 0 & \pmod{x^{\frac{n}{2}}}\\ \text{两边平方，得到} (g(x)-g_0(x))^2 & \equiv 0 & \pmod{x^{n}}\\ g^2(x)-2g(x)g_0(x)+g_0^2(x) & \equiv 0 & \pmod{x^{n}}\\ \text{两边同乘f(x)，得到} g(x)-2g_0(x)+g_0^2(x) \times f(x) & \equiv 0 & \pmod{x^{n}}\\ g(x) & \equiv 2g_0(x)-g_0^2(x) \times f(x) & \pmod{x^{n}} \end{aligned}$

于是我们得到了$g(x) \equiv 2g_0(x)-g_0^2(x) \pmod{x^{n}}$，就可以倍增了。

倍增起点是$g(x)=1 \pmod{x}$，倍增终点是$k>n$，$k=2^i$，就是我们在倍增时候的那个次数。

复杂度：$T(n)=T(\frac{n}{2})+O(n \log n)$得到最终复杂度为$O(n \log n)$

多项式除法

多项式除法同样是在$\bmod x^k$的意义下进行的。

假设我们现在已知$n$次多项式$f(x)$和$m$次多项式$g(x)$，现在请求出多项式$h(x)$和$r(x)$，满足下列两个条件

$f(x) \equiv g(x) \times h(x) +r(x) \pmod{x^{n+1}}$
$h(x)$的次数为$n-m$，$r(x)$的次数小于$m$

我们来考虑一个操作：

另$g(x)=x^nf(\frac{1}{x})$，则不难发现，其实$g(x)$的系数就是将$f(x)$的系数翻转过来了。

我们设$\hat f(x)=x^n f(\frac{1}{x})$

那么我们不妨这样处理：

$\begin{aligned} f(x) & \equiv g(x) \times h(x) +r(x) & \pmod{x^{n+1}} \\ f(\frac{1}{x}) & \equiv g(\frac{1}{x}) \times h(\frac{1}{x}) +r(\frac{1}{x}) & \pmod{x^{n+1}} \\ x^nf(\frac{1}{x}) & \equiv x^n g(\frac{1}{x}) \times h(\frac{1}{x}) + x^nr(\frac{1}{x}) & \pmod{x^{n+1}} \\ x^nf(\frac{1}{x}) & \equiv x^m g(\frac{1}{x}) \times x^{n-m} h(\frac{1}{x}) + x^nr(\frac{1}{x}) & \pmod{x^{n+1}} \\ \hat f(x) & \equiv \hat g(x) \times \hat h(x) +x^{n-m+1} \hat r(x) & \pmod{x^{n+1}} \\ \text{接下来在} & \bmod x^{n-m+1}\text{的意义下进行} \\ \hat f(x) & \equiv \hat g(x) \times \hat h(x) & \pmod{x^{n-m+1}} \\ \hat h(x) & \equiv \hat f(x) \times \hat g^{-1}(x) & \pmod{x^{n-m+1}} \\ \end{aligned}$

于是我们就求出来了$h(x)$，那么显然有$r(x) \equiv f(x) - g(x) \times h(x)$

复杂度显然与多项式求逆一致。

多项式求导

$[x^i]f'(x)=(i+1) \times [x^{i+1}]f(x)$

$\mathcal{O}(n)$

多项式积分

$[x^i]\int f(x) = \frac{1}{i}[x^{i-1}]f(x)$

$\mathcal{O}(n)$

多项式牛顿迭代

在这个问题中，我们已知函数$f(x)$，现在要求函数$g(x)$，使得$f(g(x)) \equiv 0 \pmod{x^{n+1}}$。

我们考虑倍增，假设我们已经求出了$g_0(x)$使得$f( g_0(x) ) \equiv 0 \pmod{x^{\frac{n}{2}}}$

我们要求$g(x)$使得$f( g(x) ) \equiv 0 \pmod{x^{n}}$

我们在$g_0(x)$出泰勒展开，我们可以得到

$\begin{aligned} f(g(x)) & = f(g_0(x)) \\ & + f'(g_0(x)) (g(x)-g_0(x)) \\ & + \frac{f''(g_0(x))(g(x)-g_0(x))^2 }{2!}\\ & + \cdots \end{aligned}$

由于我们在$\bmod x^{n}$的意义下进行，并且$g(x)-g_0(x)$的只有前$\frac{n}{2}$项不为$0$，

所以从第三项开始的东西都被消去了。

于是得到

$\begin{aligned} f(g(x)) & \equiv f(g_0(x)) + f'(g_0(x)) (g(x)-g_0(x)) \pmod {x^n}\\ 0 & \equiv f(g_0(x)) + f'(g_0(x)) (g(x)-g_0(x)) \pmod {x^n}\\ g(x) & \equiv g_0(x) - \frac{f(g_0(x))}{f'(g_0(x))} \pmod {x^n}\\ \end{aligned}$

就可以了

多项式ln

多项式ln可以看成将多项式带入了麦克劳林级数中。

具体定义是：

$\ln (1 - A(z)) = -\sum_{i \geq 1} \frac{A^i(z)}{i}$

也就是说，我们在计算$\ln f(x)$时，必须满足$[x^0]f(x)=1$。

接下来考虑怎么做。

$\begin{aligned} g(x) & \equiv \ln(f(x)) \pmod {x^{n+1}} \\ g'(x) & \equiv \frac{f'(x)}{f(x)} \pmod {x^{n+1}} \end{aligned}$

最后再将$g$积分回去即可。

只需要多项式求逆+多项式求导/积分。

复杂度$O(n \log n)$

多项式exp

多项式exp可以看成将多项式带入了麦克劳林级数中。

具体定义是：

$\exp(A(z)) = e^{A(z)} = \sum_{i \geq 0} \frac{A^i(z)}{i!}$

设$g(x)=e^{f(x)}$，两边取对数，得到$\ln g(x)=f(x)$，进一步可得到$ln(g(x))-f(x)=0$

也就是说，我们现在有函数$h(x)=ln(x)-f(z)$，现在要求$g(x)$使得$h(g(x))=0$。

显然有$h’(x)=\frac{1}{x}$，也就是说$h’(g(x))=\frac{1}{g(x)}$。

根据牛顿迭代的理论，这东西显然是要倍增的，并且能够得到递推式

$\begin{aligned} g(x) & \equiv g_0(x) - \frac{h(g_0(x))}{h'(g_0(x))} & \pmod {x^n} \\ g(x) & \equiv g_0(x) - h(g_0(x)) \times g_0(x) & \pmod {x^n} \\ g(x) & \equiv g_0(x) \times (1 - h(g_0(x))) & \pmod {x^n} \\ \text{带入}&h(x)\text{的定义，得到} \\ g(x) & \equiv g_0(x) \times (1 - \ln (g_0(x)) + f(x)) & \pmod {x^n} \\ \end{aligned}$

于是就可以递推了。

复杂度$O(n \log n)$

所有代码均可以在这里找到

多项式开根

算法一：$\sqrt{f(x)}=e^{\frac{1}{2} \ln f(x)}$

算法二：牛顿迭代

我们现在要求$g(x)$使得$g^2(x)=f(x)$。

构造函数$h$满足$h(g(x))=g^2(x)-f(x)$，问题转化为了求$g(x)$满足$h(g(x))=0$。

假设我们已经得到了$\pmod {x^\frac{n}{2}}$时的答案$g_0(x)$

直接套用牛顿迭代的式子，我们可以得到

$\begin{aligned} g(x) & \equiv g_0(x) - \frac{f(g_0(x))}{f'(g_0(x))} \pmod {x^n} \\ g(x) & \equiv g_0(x) - \frac{g_0^2(x)-f(x)}{2g_0(x)} \pmod {x^n} \\ g(x) & \equiv \frac{g_0^2(x)+f(x)}{2g_0(x)} \pmod {x^n} \end{aligned}$

倍增的起点是$n=1$，一般来说，$f(x)$ 的常数项为1或0，否则需要计算二次剩余。