“哇，多项式好难 背 写啊！”
“快收下这份多项式全家桶背诵指南！”
这里不细讲代码原理，只讲如何在考场上快速而准确地写出来。
关于数组清理
多项式算法要用到很多数组，并且算法之间常常嵌套，有效清理数组是防止 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]（这么写是奇技淫巧，正常应该像下面这么写）。
rev[i]=(rev[i>>1]>>1),(i&1)?(rev[i]|=hig):(0);
如果考场上把这个递推忘了，再推一遍也不是很难，所以我也不担心这个。
我担心的是什么呢，是 NTT 的主算法，这里面细节比较多。下面对着一份 NTT 进行讲解。
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 在这个班里交换完礼物后主循环结束。
话不多说，我们再看一次代码。
//一开始 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) 的二次剩余。关于二次剩余，详见这里。
多项式除法
首先是一个神奇的变换。若 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 【模板】常系数齐次线性递推，这篇题解是一个很好的参考。
多项式三角函数
其实就是用了三角函数的解析定义，\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}}。
于是这篇文章到此就告一段落了，祝多项式编码愉快！（大雾）