参考 cmd。
乘法
NTT，不说。
求逆
倍增。
考虑 \(A(x)=\frac{1}{f(x)}\bmod x^n\)，已经求得 \(B(x)=A(x)\bmod x^{\lceil \frac{n}{2} \rceil}\)。
\(A(x)-B(x)=0\pmod{x^{\lceil \frac{n}{2} \rceil}}\)
\((A(x)-B(x))^2=0\pmod{x^n}\)
\(A^2(x)-2A(x)B(x)+B^2(x)=0\pmod{x^n}\)
两边同乘 \(f(x)\):
\(A(x) - 2B(x) + B^2(x)f(x)=0\pmod{x^n}\)
即 \(A(x)=2B(x)-B^2(x)f(x)\)。
牛顿迭代
已知 \(G(x)\)，求 \(F(x)\) 使 \(G(F(x))=0\pmod{x^n}\)。
同样倍增，已经求得 \(B(x)=F(x)\pmod{x^{\lceil \frac{n}{2}\rceil}}\)。
那么 \(F(x)=B(x)-\frac{G(B(x))}{G(B'(x))} \pmod{x^n}\)
证明：
考虑泰勒展开：\(G(F(x))=G(B(x))+\sum_{k=1}^{\infty}\frac{(F(x)-B(x))^kG^{(k)}(B(x))}{k!}\)
发现当 \(k\ge2\) 后面的式子为 \(0\)，那么 \(G(F(x))=G(B(x))+(F(x)-B(x))G'(B(x))\)，推一下式子就和上面的一样了。
\(\ln\)
可知 \(\ln'(x)=\frac{1}{x}\)。
设 \(G(x)=\ln(F(x))\)，两边同时求导 \(G'(x)=\frac{F'(x)}{F(x)}\)。得到 \(G'(x)\) 算回 \(G(x)\) 就好了。
\(\exp\)
\(B(x)=\exp(F(x))\)，那么 \(F(x)=\ln(B(x))\)，\(G(B(x))=\ln(B(x))-F(x)\)。
开根
\(B(x)=\sqrt{F(x)}\)，那么 \(F(x)=B^2(x)\)，\(G(B(x))=B^2(x)-F(x)\)。
快速幂
\(F^k=\exp(k\ln(F))\)。