多项式全家桶背诵指南
Sweetlemon
2020-06-16 15:13:38
“哇，多项式好难 ~~背~~ 写啊！”
“快收下这份多项式全家桶背诵指南！”
这里不细讲代码原理，只讲如何在考场上快速而准确地写出来。
### 关于数组清理
多项式算法要用到很多数组，并且算法之间常常嵌套，有效清理数组是防止 TLE 或 WA 的保障。
我采用的协议是：调用函数之前需要保证输出数组和临时数组是（完全）干净的，调用函数之后，函数保证临时数组和输出数组的非输出部分是干净的。这样，只要注意在主函数中不要把脏的数组传给算法函数作为输出即可。
### 多项式乘法
多项式的基础当然是 FFT/NTT 优化的多项式乘法了。由于很多时候我们需要用到的是 NTT，因此这里主要背 NTT。
NTT 优化多项式乘法的主要流程是：求次数界（大于 $\deg f+\deg g$ 的最小的 $2$ 的幂），计算每个数的翻转（`rev` 数组），对两个多项式分别进行 NTT，把 NTT 的结果乘起来，对乘积进行 NTT 逆变换。
先看看前两步，需要注意的只有一个递推 `rev[i]=(rev[i>>1]>>1)|rev[i&1]`（这么写是奇技淫巧，正常应该像下面这么写）。
```cpp
rev[i]=(rev[i>>1]>>1),(i&1)?(rev[i]|=hig):(0);
```
如果考场上把这个递推忘了，再推一遍也不是很难，所以我也不担心这个。
我担心的是什么呢，是 NTT 的主算法，这里面细节比较多。下面对着一份 NTT 进行讲解。
```cpp
void NTT(int *arr,int n,int is_rev){
//初始化复制
for (int i=0;i<n;i++)
tp[i]=arr[rev[i]];
int tg=(is_rev)?(GINV):(G);
//主循环
for (int cpdis=1;cpdis<n;cpdis<<=1){
int clssiz=cpdis<<1;
int omg=kasumi(tg,MODPOW/clssiz);
for (int cpst=0;cpst<n;cpst+=clssiz){
for (int cpid=0,omega=1;cpid<cpdis;cpid++,omega=1ll*omega*omg%MOD){
int cpa=cpst+cpid;
int cpb=cpa+cpdis;
int aval=tp[cpa];
int bval=1ll*tp[cpb]*omega%MOD;
tp[cpa]=aval+bval,MD(tp[cpa]);
tp[cpb]=aval+MOD-bval,MD(tp[cpb]);
}
}
}
//答案复制
if (is_rev){
int ninv=kasumi(n,MODINV);
for (int i=0;i<n;i++)
arr[i]=1ll*tp[i]*ninv%MOD;
}
else
for (int i=0;i<n;i++)
arr[i]=tp[i];
}
```
可以看到，NTT 的函数可以分为三小段：初始化复制、主循环和答案复制。三步各有需要注意的地方。
初始化复制是把系数复制到翻转后的下标中，同时一定要**根据是正变换还是逆变换选用 $G$ 或 $G^{-1}$**。如果逆变换时使用了 $G$ ，计算 $(x^2+2x+1)^2$ 时可能得到 $x^4+1$。
主循环的过程比较复杂，它的流程可以认为是下面这样。
若（乘积的）次数界为 $n$，则我们把这些系数组成 $\dfrac{n}{2}$ 对 cp，即 $(0,1),(2,3),\cdots,(n-2,n-1)$。
一开始每对 cp 一个班，那么 cp 间的距离就只有 $1$（两人相邻）。他们相互交换礼物，即设交换前男生的数字是 $a$，女生的数字是 $b$，那么交换后男生的数字是 $a+\omega b$，女生的数字是 $a+\omega' b$；当然为了体现他们心意相通，$\omega'$ 其实就是 $\omega$的相反数；也就是交换后女生的数字实际上是 $a-\omega b$。
交换礼物后，学校把相邻的两个班合并起来，合并班级后由于某种原因，同一个班的男生和女生要分别坐在一起，那么 cp 的位置就变成了 $(0,2),(1,3);(4,6),(5,7);\cdots$，因此 cp 间的距离就成了 $2$。但这并不能阻止他们交换礼物。当然，班级里每对 cp 都希望有自己独特的美好回忆，因此他们所用的 $\omega$ 不太一样；具体地说，班里每个人都有自己的一个 $\omega$，按坐的位置顺序依次为 $\omega_0^0,\omega_0^1,\omega_0^2,\omega_0^3$；而注意到 $(0,2)$ 是一对 cp，cp 心意相通，所用的 $\omega$ 互为相反数，因此实际上 $\omega_0^2=-1$；简而言之，相邻两对 cp 所用 $\omega$ 的比是 $G$ 的 $\dfrac{998244352}{\mathrm{class\ size}}$ 次方，其中 $\mathrm{class\ size}$ 是每个班的人数，也就是 cp 对数的两倍。
每个班的 cp 交换礼物是独立的，因此要一个一个班地处理。
每个班都交换好礼物之后，学校又要合并班级，接着又继续交换礼物，直到最后只剩一个班，所有 cp 在这个班里交换完礼物后主循环结束。
话不多说，我们再看一次代码。
```cpp
//一开始 cp 间的距离是 1，cp 间的距离也就等于一个班级的男生（或女生）数
//cpdis 等于 n/2 就说明班级已经合并成一个，在这个班级里交换一次礼物，循环就可以结束了
for (int cpdis=1;cpdis<n;cpdis<<=1){
int clssiz=cpdis<<1; //班级人数=男生数（女生数）*2
int omg=kasumi(tg,MODPOW/clssiz); //班里每个人都要有一个 omega，因此是除以 clssiz
//clsst 表示这个班的学号从哪里开始，每次加 clssiz（班级人数）
for (int clsst=0;clsst<n;clsst+=clssiz){
//一共有 cpdis 对 cp（cp 数=男生人数=女生人数）
//每对 cp 中男生的 omega 从 1 开始，每次乘以 omg
for (int cpid=0,omega=1;cpid<cpdis;cpid++,omega=1ll*omega*omg%MOD){
int cpa=clsst+cpid; //男生学号
int cpb=cpa+cpdis; //女生学号
int aval=tp[cpa]; //男生的数值
int bval=1ll*tp[cpb]*omega%MOD; //女生的数值（乘以 omega）
//交换礼物
tp[cpa]=aval+bval,MD(tp[cpa]);
tp[cpb]=aval+MOD-bval,MD(tp[cpb]);
}
}
}
```
怎么样，记住了吗？
再强调一个易错点，`omg=kasumi(tg,MODPOW/clssiz)`，这里的 $\mathrm{class\ size}$ 如果写成 $\mathrm{cp\ dis}$，计算 $(x^2+2x+1)^2$ 时可能得到 $4x^4+4x^3+2x^2+4x+2$。
最后的答案复制，一定要注意，如果是逆变换，复制回去的时候要除以次数界 $n$，否则计算 $(x^2+2x+1)^2$ 时可能得到 $8x^4+32x^3+48x^2+32x+8$（这个看着够明显了吧）。
总结一下，三个易错点，其中一个是涉及 $\omega$ 的次数的，两个是逆变换时要注意的（记得**逆变换有两个地方要用逆元**）。
这样我们就把 NTT 背得滚瓜烂熟啦！~~狗粮好吃吗？~~
### 多项式求（乘法）逆
多项式求逆的任务，就是给定一个多项式 $f$，求多项式 $g$ 使得 $fg\equiv 1\pmod{x^m}$。
常用的方法是倍增法。首先我们可以轻易求得 $m=0$ 时的答案，也就是 $a_0^{-1}$（常数项的逆元）。
下面假设我们已经知道多项式 $g$，使得 $fg\equiv 1\pmod{x^n}$，那么如何求多项式 $h$，使得 $fh\equiv 1\pmod{x^{2n}}$ 呢？
我们推一推式子。$fg\equiv 1\pmod{x^n}\Leftrightarrow fg-1\equiv 0\pmod{x^n}$，也就意味着 $fg-1$ 有因子 $x^n$。可设 $fg-1=x^n\cdot A$。
两边平方，得到 $(fg-1)^2=x^{2n}\cdot A$，因此 $(fg-1)^2\equiv 0\pmod{x^{2n}}$（绕了一圈不过是说明了这个可以直接平方）。
用完全平方公式打开得到 $f^2g^2-2fg+1\equiv 0$，由于要求逆元，因此把 $1$ 放在一边得到 $2fg-f^2g^2\equiv 1$；把 $f$ 提出来得到 $f(2g-fg^2)\equiv 1\pmod{x^{2n}}$。于是，所求 $h\equiv 2g-fg^2=g(2-fg)\pmod{x^{2n}}$。
所以只需要计算出 $g(2-fg)$ 就可以作为答案了。不断倍增，直到 $n\ge m$，把最后得到的逆的前 $m$ 项（即 $\bmod\ x^m$）输出即可。
貌似很简单？要注意易错点啊。
第一个易错点是，计算 $h$ 时的次数界不是 $2n$。在计算 $h$ 时，$f$ 需要取它的前 $2n$ 项；而 $g$ 的次数界是 $n$，因此这个式子的最高次 $fg^2$ 应该是 $(2n-1)+(n-1)+(n-1)$，次数界是 $4n$。如果这个次数界不对，那么算不出正确的乘积。
第二个易错点是，算完 $g$（即 $h$）后，由于次数界是 $4n$，因此需要把 $x^{2n}$ 一直到 $x^{4n-1}$ 的系数全部清零，即模 $x^{2n}$。否则 $g$ 的次数界会变大，下一次倍增时乘法可能就会出问题。当然计算完毕后最好也记得把 $[m,n)$ 部分的系数清空，为其他函数调用多项式求逆作好准备。
还有就是注意数组的大小。假设不小于 $m$ 的最小 $2$ 的幂是 $t$，那么最后一次倍增时的次数界是 $2t$，因此数组要不小于 $2t$。
### 多项式求 $\ln$
给定多项式 $f$，且 $f(0)=1$，求 $g\equiv \ln f(x) \pmod{x^n}$。
这个问题并不困难。两边求导得到 $g'\equiv \dfrac{f'(x)}{f(x)}$，因此求出 $f(x)$（模 $x^n$ 的）逆元，乘以 $f'(x)$（这两个的次数界都是 $n$，因此这次乘法次数界是 $2n$），最后积分即可。由于 $f(0)=1$，所以积分常数 $C=0$。
数组大小与多项式求逆的 $2t$ 相等。还有一个需要注意的地方是，数组要清理干净，在次数界范围内不要有多余的东西（比如上一次 NTT 留下来的值等等）。
### 多项式求 $\exp$
给定多项式 $f$，且 $f(0)=0$，求 $g\equiv \exp f(x) = \mathrm{e}^{f(x)} \pmod{x^n}$。
这个问题比多项式 $\ln$ 要难，因为我们不能直接两边求导——$g'(x)\equiv f'(x)\mathrm{e}^{f(x)}$，怎么求导都消不掉 $g(x)$。
我们要求的是 $g\equiv \exp f(x)$，也就是想让 $\ln g - f(x)\equiv 0$。接下来要用的技术是多项式牛顿迭代。
先回忆一下普通的牛顿迭代（高考有时候喜欢考）。给定初始点 $x_0$，求 $h(x)$ 的一个零点，只需不断作 $x=x_0$ 处的切线，把 $x_0$ 调整成切线与 $x$ 轴的交点，重复上述过程即可。切线的方程是 $y-h(x_0)=h'(x_0)(x-x_0)$，因此可以解得 $x_1=x_0-\dfrac{h(x_0)}{h'(x_0)}$。
多项式牛顿迭代与此类似，不过“自变量”不是 $x$，而是多项式。经过一些推导过程，我们知道，如果已知 $h(g_0)\equiv 0\pmod{x^{\lceil \frac{n}{2} \rceil}}$，那么我们有 $g\equiv g_0-\dfrac{h(g_0)}{h'(g_0)}\pmod{x^n}$。注意两点：一是计算 $g$ 的式子中每一项（求导、求逆）都需要 $\bmod x^n$ 进行；二是 $h'(g_0)$ 是对 $g_0$ 求导而不是对 $x$ 求导，因此无需链式法则。
在多项式 $\exp$ 中，$h(g)=\ln g-f$（$f$ 已知）。那么 $h'(g)=\dfrac{1}{g}$，$g\equiv g_0-(\ln g_0-f)\cdot g_0=g_0(f-\ln g_0+1) \pmod{x^n}$。因此回溯的时候对 $g_0$ 求 $\ln$，代入计算即可得 $g$。
由于这里不是倍增而是牛顿迭代，因此我们可以采用递归写法。
### 多项式快速幂
给定 $n-1$ 次多项式 $f$，且 $f(0)=1$，求 $(f(x))^m \pmod{x^n}$ 的值。$1\le m\le 10^{100000}$。
首先解决最棘手的问题：$m$ 这么大，怎么办？这里有一个好消息，$(f(x))^m\equiv (f(x))^{m\bmod p}$。
为什么呢？有两种证明方法。
方法一，两边同时取对数（因为两边的常数项都是 $1$，因此模意义下对数存在），那么 $m\ln f(x)\equiv (m\bmod p)\ln f(x)$，这个确实成立。
方法二，先证明一个引理：$(f(x))^p\equiv f(x^p)$。
对次数用数学归纳法。首先 $1^p\equiv 1^p$。接下来设 $f(x)=1+a_1x+a_2x^2+\cdots+a_{n-1}x^{n-1}$，且设 $g(x)=\dfrac{f(x)-1}{x}=a_1+a_2x+a_3x^2+\cdots+a_{n-1}x^{n-2}$，那么 $(f(x))^p\equiv (1+xg(x))^p\equiv \sum_{i=0}^{p}\mathrm{C}_p^i (xg(x))^i\equiv 1+(xg(x))^p$，最后一步用到了卢卡斯定理（$\forall 0<t<p,\mathrm{C}_p^t\equiv 0$）。因此 $(f(x))^p\equiv 1+x^p(g(x)^p)$。$g$ 的次数比 $f$ 小 $1$，由归纳假设可得 $(f(x))^p\equiv 1+x^pg(x^p)\equiv f(x^p)$。引理证毕。
由于 $n<p$，因此 $x^p$ 这一项会被模 $x^n$ 模掉，因此 $(f(x))^p\equiv 1\pmod{x^n}$。一定要注意是**前 $n$ 项系数**相等，而不是多项式的值相等！
这样，我们对 $m$ 边读入边取模，终于把 $m$ 压缩到了 $p$ 以下。
接下来怎么做呢？最简单的做法当然是使用经典快速幂来乘啦。但是注意：**不能**一遍 NTT 之后对每个点值进行快速幂，再逆变换回来！原因是，NTT 实际上是循环卷积，我们只是用循环卷积模拟多项式乘法，因此卷积长度必须大于结果多项式的次数。那怎么办呢？只能每乘一次就逆变换回来，并且每乘一次都要对 $x^n$ 取模。时间复杂度 $\mathrm{O}(n \log n \log p)$。
更快的做法正如上面的方法一所述，先 $\ln$，乘 $m$ 再 $\exp$，$\mathrm{O}(n\log n)$。
这个还有加强版，不保证 $f(0)=1$，怎么办呢？
我们分两种情况讨论。若 $f(0)\neq 0$，那么所有项系数除以 $f(0)$ 就能实现 $f(0)=1$，快速幂后再乘回 $(f(0))^m$ 即可。注意这个快速幂中 $m$ 要模 $p-1$ 而不是 $p$。
若 $f(0)=0$，那么我们不断提出 $x$，直到 $f(0)\neq 0$；最后再乘回去就好了。
### 多项式开根
用的方法还是多项式牛顿迭代，式子是 $g\equiv \dfrac{1}{2} \left( g_0 + \dfrac{f}{g_0} \right)$，写法类似多项式 $\exp$。由于不需要调用 $\ln$ 和 $\exp$，因此可以借用它们的临时数组。
这个式子中，其实只需要对 $f$ 和 $g_0^{-1}$ 做 NTT，把它们乘起来再加上 $g_0$ 并除以 $2$ 即可。
当然，这里有一个小问题：$n=1$ 时，$g_0$ 应为 $f(0)$ 的二次剩余。关于二次剩余，详见[这里](https://www.luogu.com.cn/blog/Sweetlemon/quadratic-residue)。
### 多项式除法
首先是一个神奇的变换。若 $f(x)$ 是 $n$ 次多项式，定义 $f_R(x)=x^nf(\frac{1}{x})$。比如 $f(x)=x^3+3x^2+2x+4$ 时，$f_R(x)=4x^3+2x^2+3x+1$。我们可以发现，$f_R$ 和 $f$ 恰好是系数倒置的关系，可以 $\mathrm{O}(n)$ 求出。`std::reverse(first,last)` 可以帮助你翻转 $[\mathrm{first},\mathrm{last})$ 的区域。
接下来就是推导了。设 $f=gq+r$，其中 $\deg(r)<\deg(g)$。记 $\deg(f)=n,\deg(g)=m\ (n\ge m)$，那么 $\deg(q)=n-m,\ \deg(r)<m$。
由于 $f=gq+r$，也就是 $f(x)=g(x)q(x)+r(x)$，令 $x=\frac{1}{x}$，得到 $f(\frac{1}{x})=g(\frac{1}{x})q(\frac{1}{x})+r(\frac{1}{x})$。两边同乘 $x^n$，$x^nf(\frac{1}{x})=x^ng(\frac{1}{x})q(\frac{1}{x})+x^nr(\frac{1}{x})$。
为了使用 $R$ 变换，把 $x^n$ 在 $g,q$ 之间巧妙分配，同时调整 $r$ 前面的 $x$，得到 $x^nf(\frac{1}{x})=(x^mg(\frac{1}{x}))(x^{n-m}q(\frac{1}{x}))+x^{n-\deg(r)}x^{\deg(r)}r(\frac{1}{x})$，这样对 $f,g,q,r$ 作 $R$ 变换可以得到 $f_R(x)=g_R(x)q_R(x)+x^{n-\deg(r)}r_R(x)$。
这个式子里还有两个未知数，我们想办法消掉一个。由于 $\deg(r)<m$，因此 $n-\deg(r)\ge n-m+1$，这样 $x^{n-\deg(r)}r_R(x)$ 的最低项次数至少是 $n-m+1$。两边同时模 $x^{n-m+1}$，$r$ 就被消掉了，得到 $f_R(x)\equiv g_R(x)q_R(x)\pmod{x^{n-m+1}}$。于是我们可以计算出 $q_R\bmod{x^{n-m+1}}$ 的值。因为 $\deg(q)=n-m<n-m+1$，所以它恰好没有损失系数，也就是 $q_R\bmod{x^{n-m+1}}=q_R$，将其作 $R$ 变换得到 $q$。最后再用 $f-gq$ 得到 $r$。
整理一下，算法的过程中，我们需要先对 $f,g$ 进行 $R$ 变换，再分别模 $x^{n-m+1}$ 后计算 $q_R\equiv f_Rg_R^{-1}\pmod{x^{n-m+1}}$，把 $q_R$ 翻转得到 $q$。最后用原来的（没有模 $x^{n-m+1}$ 的）$f,g$ 计算 $r$，$r=f-gq$。
这里只用到了几次线性的翻转、一次求逆和几次乘法，属于常数不太大的 $\mathrm{O}(n\log n)$。其实这个算法并不难，不过实现过程中要有效地利用数组。
做出这道题之后可以做 [P4723 【模板】常系数齐次线性递推](https://www.luogu.com.cn/problem/P4723)，[这篇题解](https://www.luogu.com.cn/blog/_post/247619)是一个很好的参考。
### 多项式三角函数
其实就是用了三角函数的解析定义，$\sin x=\dfrac{\mathrm{e}^{\mathrm{i}x}-\mathrm{e}^{\mathrm{-i}x}}{2\mathrm{i}},\cos x=\dfrac{\mathrm{e}^{\mathrm{i}x}+\mathrm{e}^{\mathrm{-i}x}}{2}$。这个定义可以由 $\mathrm{e}^{\mathrm{i}x}=\cos x+\mathrm{i}\sin x$ 得到。
### 多项式反三角函数
这道题的解法和多项式三角函数没有任何关系。
这题是用了 $\arcsin$ 和 $\arctan$ 的导数不是三角函数这一特点来做的（与此相对，$\sin$ 和 $\cos$ 的导数还是三角函数，因此不能利用导数做）。因为 $g=\arcsin f$，所以 $g'=\dfrac{f'}{\sqrt{1-f^2}}$；或因为 $g=\arctan f$，所以 $g'=\dfrac{f'}{f^2+1}$。套用多项式乘法、开根、求逆、求导、积分就可以了。
这里稍微推导一下用到的两个导数 $(\arcsin x)'=\dfrac{1}{\sqrt{1-x^2}}$ 和 $(\arctan x)'=\dfrac{1}{x^2+1}$。
设 $x=\sin y$，两边对 $x$ 求导得到 $1=\dfrac{\mathrm{d}y}{\mathrm{d}x}\cos y$，于是 $\dfrac{\mathrm{d}y}{\mathrm{d}x}=\dfrac{1}{\cos y}$。因为 $\arcsin$ 的值域是 $\left[-\dfrac{\pi}{2},\dfrac{\pi}{2}\right]$，因此 $\cos y\ge0$，$\cos y=\sqrt{1-\sin^2y}=\sqrt{1-x^2}$。由此我们得出了 $\dfrac{\mathrm{d}y}{\mathrm{d}x}=\dfrac{1}{\sqrt{1-x^2}}$。
$\arccos$ 的解法是类似的。下面求 $\arctan$ 的导数。设 $x=\tan y$，两边对 $x$ 求导得到 $1=\dfrac{\mathrm{d}y}{\mathrm{d}x}\dfrac{1}{\cos^2y}$ ，于是 $\dfrac{\mathrm{d}y}{\mathrm{d}x}=\cos^2y=\dfrac{\cos^2y}{\sin^2y+\cos^2y}=\dfrac{1}{\tan^2y+1}=\dfrac{1}{x^2+1}$。最后几步用的是高中很常用的三角函数二次式化简技巧，上下齐次同除 $\cos^2$。
于是这篇文章到此就告一段落了，祝多项式编码愉快！（大雾）