前言

还记得上个学期tututu跟我提过多项式的很多操作，还有一些优化常数的奇技淫巧，然而那个时候我一脸懵逼。最近几天无所事事，去洛谷做比赛又整天被吊着打，闲暇之余就想着学一下多项式的几个基本操作。 其实一开始我是想学CZT的，根据myy的论文它能把BZOJ3992那题优化到O(mlog⁡(m)+mlog⁡(n))" role="presentation" style="position: relative;">O(mlog(m)+mlog(n))$O(m\log (m)+m\log (n))$。然而它的应用面不广我就很功利地没有学。还有如何用两次DFT求实序列的卷积等等。至于多项式牛顿迭代法，生成函数之类的，等我补完高数再回来学吧。说不定以后会填这些坑 多项式求逆，取模及开方应该算是多项式最为常见的应用，主要配合生成函数，常系数线性齐次递推优化一起用。虽然已经有很多dalao们写过详细的笔记，不过这些算法的题目比较少，我怕太久没写就忘了，所以还是自己写(shui)一篇QAQ。

---

多项式求逆：

定义：

给出多项式A(x)" role="presentation" style="position: relative;">A(x)$A(x)$，现要求一个多项式B(x)" role="presentation" style="position: relative;">B(x)$B(x)$，使得： A(x)B(x)≡1(modxn)" role="presentation" style="text-align: center; position: relative;">A(x)B(x)≡1(modxn)$$A(x)B(x)\equiv 1(\mathrm{mod}{x}^n)$$ 为什么要模xn" role="presentation" style="position: relative;">xn$x^n$？如果不在模xn" role="presentation" style="position: relative;">xn$x^n$意义下定义逆元，除非A(x)" role="presentation" style="position: relative;">A(x)$A(x)$只有常数项，否则根据二项式定理，B(x)" role="presentation" style="position: relative;">B(x)$B(x)$有无穷多项。 模xn" role="presentation" style="position: relative;">xn$x^n$，换句话说就是把多项式A(x)B(x)" role="presentation" style="position: relative;">A(x)B(x)$A(x)B(x)$的n次方及更高次项截断。

暴力：

考虑如何暴力求逆。 令C(x)=A(x)∗B(x)" role="presentation" style="position: relative;">C(x)=A(x)∗B(x)$C(x)=A(x)\ast B(x)$。由于A0B0=C0=1" role="presentation" style="position: relative;">A0B0=C0=1$A_0{B}_0=C_0=1$，可得B0" role="presentation" style="position: relative;">B0$B_0$为A0" role="presentation" style="position: relative;">A0$A_0$的逆元。又因为A0B1+A1B0=C1=0" role="presentation" style="position: relative;">A0B1+A1B0=C1=0$A_0{B}_1+A_1{B}_0=C_1=0$，可以解得B1=−A1B0A0" role="presentation" style="position: relative;">B1=−A1B0A0$B_1=\frac{-A_1{B}_0}{A_0}$。依此类推，即可解出B0" role="presentation" style="position: relative;">B0$B_0$至Bn−1" role="presentation" style="position: relative;">Bn−1$B_{n-1}$。解到Bn−1" role="presentation" style="position: relative;">Bn−1$B_{n-1}$即可停止，因为求逆在模xn" role="presentation" style="position: relative;">xn$x^n$意义下进行。 同时我们可以看出，多项式A(x)" role="presentation" style="position: relative;">A(x)$A(x)$是否存在逆元B(x)" role="presentation" style="position: relative;">B(x)$B(x)$，只取决于A0" role="presentation" style="position: relative;">A0$A_0$是否有逆元，因为每次求Bi" role="presentation" style="position: relative;">Bi$B_i$的时候，分母的位置总是A0" role="presentation" style="position: relative;">A0$A_0$。在下面O(nlog⁡(n))" role="presentation" style="position: relative;">O(nlog(n))$O(n\log (n))$的算法中，同样可以证明这一点。

倍增：

为了方便，下面假设n=2k(k>0)" role="presentation" style="position: relative;">n=2k(k>0)$n=2^k(k>0)$。如果实际操作中n不是2的幂，像FFT那样将n强行增大到2的幂即可。如果n=1，直接求A0" role="presentation" style="position: relative;">A