多项式乘法逆元
定义
对于多项式 $f(x)$（常数项系数不为 $0$），若存在 $g(x)$ 满足：
$$\begin{aligned} f(x) g(x) & \equiv 1 \pmod{x^{n}} \end{aligned}$$
则称 $g(x)$ 为 $f(x)$ 在模 $x^{n}$ 意义下的 逆元（Inverse Element），记作 $f^{-1}(x)$。若要求 $\operatorname{deg}{g} < n$，则此时 $g$ 唯一。
牛顿法
推导过程
求$$F(x)G(x)\equiv1\ ({\rm mod}\ x^n)$$
当 $n=1$ 时，$A(x) \equiv c \pmod x$，$c$ 是一个常数，那么 $A^{-1}(x)=c^{-1}$。
对于 $n>1$ 的情况，令
$$F(x)G_1(x) \equiv 1 \pmod {x^{\lceil \frac{n}{2} \rceil}}$$
作差可得
$$F(x)(G(x)-G_1(x)) \equiv 0 \pmod {x^{\lceil \frac{n}{2} \rceil}}$$
除去 $F(x)$，得
$$G(x)-G_1(x) \equiv 0 \pmod {x^{\lceil \frac{n}{2} \rceil}}$$
两边平方，得
$$(G(x)-G_1(x))^2 \equiv 0 \pmod {x^n}$$
展开有
$$G^2(x)-2G(x)G_1(x)+G^2_1(x) \equiv 0 \pmod {x^n}$$
同时乘上 $F(x)$，由定义，有
$$G(x)-2G_1(x)+F(x)G_1^2(x) \equiv 0 \pmod {x^n}$$
求得递归式
$$G(x) \equiv 2G_1(x)-F(x)G_1^2(x) \pmod {x^n}$$
再提取一下公因式
$$G(x) \equiv G_1(x)(2-F(x)G_1(x)) \pmod {x^n}$$
化简为常数项后直接求逆元即可。
时间复杂度为 $T(n)=T(\frac{n}{2})+O(n \log n)=O(n \log n)$。
代码实现
模板题：Luogu P4238。
递归版
迭代版
高度封装迭代版
任意模数
模板题：Luogu P4239。
整合一下任意模数多项式乘法和牛顿迭代法，注意多项式乘法可以分步进行，避免超出中国剩余定理可以计算的范围。注意代码常数。