Polynomial_Industry
方便复习直接把重要的式子放在前面：
- 求逆，采用倍增，式子（牛顿迭代记忆可能比较方便？）：
$$B(x)\equiv 2B_\ast(x)-B^2_\ast(x)A(x)\pmod{x^n}$$
- 求导、积分与复合，即经典求导、积分与复合，式子：
$$F’(x)=\sum_{i=0}^{\infty}if_ix^{i-1}$$
$$F’(x)=C+\sum_{i=0}^{\infty}\dfrac{f_i}{i}x^{i+1}$$
$$F(G(x))=\sum_{i=0}^{\infty}f_iG^i(x)$$
- 牛顿迭代（非常重要）：
$$F(x)\equiv F_\ast(x)-\dfrac{G(F_\ast(x))}{G’(F_\ast(x))}\pmod{x^n}$$
- 开根，采用倍增（可以用牛顿迭代直接推）：
$$B(x)\equiv \dfrac{A(x)+B^2_\ast(x)}{2B_\ast(x)}\pmod{x^n}$$
- 多项式带余除法（换元翻转再取余）：
$$Q^T(x)\equiv F^T(x)G^T(x)^{-1}\pmod{x^{n-m+1}}$$
$$R(x)=F(x)-Q(x)G(x)$$
- 多项式 $\ln$（两边求导再积分）：
$$\ln F(x)=-\sum_{i=0}^{\infty}\dfrac{(1-F(x))^i}{i}$$
$$B(x)=\int\dfrac{A’(x)}{A(x)}$$
- 多项式 $\exp$，采用倍增（牛顿迭代推）：
$$B(x)\equiv B_\ast(x)(1-\ln B_\ast(x)+A(x))\pmod{x^n}$$
- 多项式快速幂：
$$A^k(x)=\exp(k\ln A(x))$$
方便粘板子直接把全家桶放 这里 了。
基本是复读 cmd 博客的。
模板题洛谷上基本都有。
占时没有 MTT 的东西（因为写不对）。。。
工业基础：NTT & FFT。
学完 NTT 后就可以来看这些操作了。
我们先把基本的模板贴在这里：
1 |
|
一、多项式求逆
递推法就不写了。。。
我们采用倍增。
首先，如果在 $\pmod{x^1}$ 的时候，多项式显然只有常数项。直接求数字逆元。
设 $R(x)$ 表示 $\pmod{x^n}$ 时 $F(x)$ 的逆。
现在，假设我们已经得到了：
$$R’(x)\equiv F^{-1}(x)\pmod{x^{\frac{n}{2}}}$$
即逆元的前 $\dfrac{n}{2}$ 位。
显然：
$$R(x)\equiv R_\ast(x)\pmod{x^{\frac{n}{2}}}$$
移项一下：
$$R(x)-R_\ast(x)\equiv0\pmod{x^{\frac{n}{2}}}$$
然后平方一下：
$$(R(x)-R_\ast(x))^2\equiv 0\pmod{x^n}$$
拆开：
$$R^2(x)-2R_\ast(x)R(x)+R_\ast^2(x)\equiv 0\pmod{x^n}$$
两边同乘 $F(x)$：
$$R(x)-2R_\ast(x)+R_\ast^2(x)F(x)\equiv 0\pmod {x^n}$$
移项：
$$R(x)\equiv2R_\ast(x)-R_\ast^2(x)F(x)\pmod {x^n}$$
显然可以算了。
根据主定理：
$$T(n)=T(n/2)+\Theta(n\log n)=\Theta(n\log n)$$
所以最后时间复杂度 $O(n\log n)$。
一个简单的实现方法是先求 $(2R_\ast)(x)$，然后求 ${R_\ast}^2(x)$（自己和自己卷），然后把 ${R_\ast}^2(x)$ 和 $F(x)$ 卷，最后两个一减。
然后可能还有什么优化方法，但是我不想用。。。
最后记得清空。
代码：
1 | // Inversion |
二、多项式牛顿迭代
关于求导、积分与复合。
定义多项式导数：
$$F’(x)=\sum_{i=0}^{\infty}if_ix^{i-1}$$
定义多项式积分：
$$F’(x)=C+\sum_{i=0}^{\infty}\dfrac{f_i}{i}x^{i+1}$$
定义多项式的复合：
$$F(G(x))=\sum_{i=0}^{\infty}f_iG^i(x)$$
积分使用前需要先线性求一波逆元。
代码：
1 | // Newton Iteration. |
关于多项式牛顿迭代：
若 $G(F(x))=0$，且 $G(F_\ast(x))\equiv 0\pmod{x^{\frac{n}{2}}}$，则我们有：
$$F(x)\equiv F_\ast(x)-\dfrac{G(F_\ast(x))}{G’(F_\ast(x))}\pmod{x^n}$$
证明：
显然 $F(x)\equiv F_\ast(x)\pmod{x^{\frac{n}{2}}}$。
将 $G(F(x))$ 在 $F_\ast(x)$ 处展开：
$$\begin{aligned}G(F(x))&=G(F_\ast(x))+\dfrac{G’(F_\ast(x))}{1!}(F(x)-F_\ast(x))
\\
&+\dfrac{G’’(F_\ast(x))}{2!}(F(x)-F_\ast(x))^2+\cdots\end{aligned}$$
可知 $F(x)-F_\ast(x)$ 的最低次项至少是 $x^{n/2}$。
可知 $(F(x)-F_\ast(x))^2,(F(x)-F_\ast(x))^3,\cdots$ 等的最低次项是 $x^n$。
但上面的运算是 $\pmod{x^n}$ 下的，所以这些项全部木大，故：
$$G(F(x))=G(F_\ast(x))+\dfrac{G’(F_\ast(x))}{1!}(F(x)-F_\ast(x))$$
因为 $G(F(x))=0$，整理一下就是上面的结论了。
这个式子很牛逼。
多项式求逆再推导
这个用牛顿迭代推导。求 $A(x)$ 的逆 $B(x)$。
那么我们就有 $A(x)B(x)\equiv 1\pmod{x^n}$。
然后我们设 $G(B(x))\equiv A(x)B(x)-1\pmod{x^n}$。
则 $G’(B(x))\equiv A(x)\pmod{x^n}$。
设 $B_\ast(x)$ 为 $\pmod{x^{n/2}}$ 下的解。
用上文牛顿迭代的式子：
$$B(x)\equiv B_\ast(x)-\dfrac{G(B_\ast(x))}{G’(B_\ast(x))}\equiv B_\ast(x)-\dfrac{A(x)B_\ast(x)-1}{A_\ast(x)}\pmod{x^n}$$
上面的 $\dfrac{1}{A_\ast(x)}$ 就是 $B_\ast(x)$，因为这俩多项式都是在 $\pmod{x^{n/2}}$ 下的。
然后就有了：
$$B(x)\equiv B_\ast(x)-B_\ast(x)(A(x)B_\ast(x)-1)\equiv 2B_\ast(x)-B_\ast^2(x)A(x)\pmod{x^n}$$
这玩意就是上面那个求逆的式子。
三、多项式开根
即 $B^2(x)-A(x)\equiv 0\pmod{x^n}$。
于是我们套路令 $G(B(x))\equiv B^2(x)-A(x)\pmod{x^n}$。
于是有 $G’(B(x))\equiv 2B(x)\pmod{x^n}$。
再根据牛顿迭代：
$$B(x)\equiv B_\ast(x)-\dfrac{G(B_\ast(x))}{G’(B_\ast(x))}\equiv B_\ast(x)-\dfrac{B^2_\ast(x)-A(x)}{2B_\ast(x)}\pmod{x^n}$$
化简后就是：
$$B(x)\equiv \dfrac{A(x)+B^2_\ast(x)}{2B_\ast(x)}\pmod{x^n}$$
这个东西可以倍增了（还要用一下求逆），时间复杂度可以用定积分推导（不关心这个的可以跳过）：
$$T(n)=\Theta(\sum_{i=0}^{\log_2 n}\dfrac{n}{2^i}\log_2 \dfrac{n}{2^i})=\Theta(n\sum_{i=0}^{\log_2 n}(\dfrac{1}{2})^i(\log_2 n-i))$$
我们积分近似一下：
$$T(n)=\Theta(n\int_{0}^{\log_2 n}(\dfrac{1}{2})^x(\log_2 n-x)\delta x)$$
积分线性性拆一下：
$$T(n)=\Theta(n\log_2 n\int_{0}^{\log_2 n}(\dfrac{1}{2})^x\delta x-n\int_{0}^{\log_2 n}x(\dfrac{1}{2})^x\delta x)$$
第一个还好，就是 $\int a^x\delta x=\dfrac{1}{\ln a}a^x+C$。
第二个我去查了一下积分表：$\int xa^x\delta x=\dfrac{x}{\ln a}a^x-\dfrac{1}{(\ln a)^2}a^x+C$。
然后这个我们就能算了：
$$T(n)=\Theta(-\dfrac{1}{\ln \frac{1}{2}}n\log_2 n-\dfrac{n}{(\ln \frac{1}{2})^2}+\dfrac{1}{\ln \frac{1}{2}})$$
注意 $\ln \dfrac{1}{2}$ 是负的，于是我们的时间复杂度就是：
$$T(n)=\Theta(n\log_2 n)$$
代码：
1 | // Squre root |
四、多项式带余除法
定义多项式带余除法，对于多项式 $F(x)$，$G(x)$，存在唯一 $Q(x)$，$R(x)$ 使得：
$$F(x)=Q(x)G(x)+R(x)$$
此时称 $Q(x)$ 为 $F(x)$ 除以 $G(x)$ 的商，$R(x)$ 为 $F(x)$ 除以 $G(x)$ 的余数（若 $Q(x)\not = 0$，需要满足 $\deg Q+\deg G=deg F$）。
我们同样可以记作：
$$F(x)\equiv R(x)\pmod{G(x)}$$
很容易想到，上面的 $R(x)$ 如果没了，这玩意就是直接多项式求逆。
那么我们就要考虑如何让 $R(x)$ 消失。
我们知道 $R(x)$ 的次数比较低，而我们前面的 $\pmod{x^{?}}$ 往往只能消去高次的项，留下低次的项。
那么很自然想到翻转系数，原来次数低的系数变成次数高的。
定义 $n$ 次多项式翻转操作 $F^T(x)=x^nF(x^{-1})$（实质上就是把系数翻转了一下）。
我们从 $F(x)=Q(x)G(x)+R(x)$ 开始，换元得到：
$$F(x^{-1})=Q(x^{-1})G(x^{-1})+R(x^{-1})$$
两边同时乘上 $x^n$：
$$x^nF(x^{-1})=x^nQ(x^{-1})G(x^{-1})+x^nR(x^{-1})$$
将我们上文定义的翻转操作代入：
$$F^T(x)=Q^T(x)G^T(x)+x^{n-m+1}R(x)$$
这个时候我们将其置入 $\pmod{x^{n-m+1}}$ 的环境下：
$$F^T(x)\equiv Q^T(x)G^T(x)\pmod{x^{n-m+1}}$$
那么商就是：
$$Q^T(x)\equiv F^T(x)G^T(x)^{-1}\pmod{x^{n-m+1}}$$
求逆之后，翻转一下系数即可。
余数就是：
$$R(x)=F(x)-Q(x)G(x)$$
时间复杂度仍然是 $O(n \log n)$。
代码：
1 | // Division with Remainder. Here f/g->f f%g->g. |
五、多项式 $\ln$，$\exp$
两者均由麦克劳林级数定义：
$$\ln F(x)=-\sum_{i=1}^{\infty}\dfrac{(1-F(x))^i}{i}$$
$$\exp F(x)=\sum_{i=0}^{\infty}\dfrac{F^i(x)}{i!}$$
这样我们的运算可以满足经典的一些性质。
多项式 $\ln$
这里我们有 $\ln A(x)=B(x)$。
两边同时求导：
$$\dfrac{\delta}{\delta x}\ln A(x)=\dfrac{\delta}{\delta x}B(x)$$
即（链式法则）：
$$\dfrac{\delta A(x)}{\delta x}\dfrac{\delta}{\delta A(x)}\ln A(x)=B’(x)$$
即：
$$\dfrac{A’(x)}{A(x)}=B’(x)$$
再两边同时积分：
$$B(x)=\int \dfrac{A’(x)}{A(x)}$$
也就是说，一次求导，一次求逆，一次相乘，一次积分，我们就得到了 $\ln A(x)$。
时间复杂度 $O(n\log n)$。
多项式 $\exp$
这里就讲一个倍增方法。
已知 $e^{A(x)}=B(x)$，即 $A(x)=\ln B(x)$。
我们设 $G(B(x))=\ln B(x)-A(x)$。
求导可得 $G’(B(x))=B^{-1}(x)$。
套路牛顿迭代：
$$B(x)\equiv B_\ast(x)-\dfrac{G(B_\ast(x))}{G’(B_\ast(x))}\equiv B_\ast(x)-\dfrac{\ln B_\ast(x)-A(x)}{B_\ast(x)^{-1}}\pmod{x^n}$$
即：
$$B(x)\equiv B_\ast(x)(1-\ln B_\ast(x)+A(x))\pmod{x^n}$$
根据上式倍增即可。
需要注意的是，必须保证 $a_0=0$，此时 $b_0=1$。
与上文多项式开根的复杂度分析类似，使用定积分可以得到 $\exp$ 的时间复杂度是 $O(n\log n)$ 的。
代码：
1 | // Ln & Exp. |
六、多项式快速幂
有了上面的操作，这个东西就变得简单了起来：
$$A^k(x)=\exp (k\ln A(x))$$
也就是说，一次 $\ln$，一次乘常系数，一次 $\exp$，我们就完成了多项式快速幂。
时间复杂度 $O(n\log n)$（与 $k$ 完全没有关系）。
关于加强版，因为巨神的码被 Hack 了，我也懒得管，所以就不做了。
代码：
1 | // Qpow. |
七、任意模数多项式乘法
咕咕咕。