前言

多项式博大精深啊……个人整理了一个易于背诵的简化版，如果想看详细证明请另寻资源（
日后可能会再开一个代码详解，用于帮助和我一样理解不了还背不过的人（
更新大致跟随真实学习进度，如果咕咕咕了也很正常（

约定

给定多项式\(F(x)=\sum\limits_{k=0}^n a_kx^k\)，非必要时会省略为\(F\)。
运算均在模意义下进行。

求逆

求\(G(x)\)使\(FG\equiv1\pmod{x^n}\)
设\(FH\equiv1\pmod{x^{n/2}}\)，又\(\because FG\equiv1\pmod{x^{n/2}}\)，
\(\therefore H-G\equiv0\pmod{x^{n/2}},\ H^2-2HG+G^2\equiv0\pmod{x^n}\)
\(F(H^2-2HG+G^2)\equiv0\pmod{x^n}\Rightarrow FH^2-2H+G\equiv0\pmod{x^n}\Rightarrow G\equiv 2H-FH^2\pmod{x^n}\)
倍增计算即可。

求导/积分

\(F'(x)=\sum\limits_{k=1}^n ka_kx^{k-1},\int F(x)\text{d}x=\sum\limits_{k=0}^n \dfrac{a_k x^{k+1}}{k+1}\)

对数函数

求\(G(x)\)使\(G\equiv\ln F\pmod{x^n}\)
两边求导得：\(G'\equiv(\ln F)'F'=F'F^{-1}\pmod{x^n}\)
对\(F\)求导、求逆，求出\(G\)来再积回去。

指数函数

前置知识：牛顿迭代

对于已知多项式\(F\)，求一个多项式\(G\)，使\(F(G(x))\equiv0\pmod{x^n}\)
假设我们现在求一个函数\(f\)的零点，那么取一个值\(x_0\)，作切线，以切线的横截距作为新的\(x_0\)，即\(x=x_0-\dfrac{f(x_0)}{f'(x_0)}\)。
对应到多项式上是一样的：假设\(F(G_0(x))\equiv0\pmod{x^{n/2}}\)，则\(G\equiv G_0-\dfrac{F(G_0)}{F'(G_0)}\pmod{x^n}\)

多项式 exp

给定多项式\(F\)，求\(G(x)\equiv e^{F(x)}\pmod{x^n}\)
求对数，得\(\ln G-F\equiv0\pmod{x^n}\)
把左侧看成一个函数\(H=\ln G-F\)，则对于\(H(G)\equiv0\pmod{x^n}\)可以牛顿迭代：
设\(H(G_0)\equiv0\pmod{x^{n/2}}\)，则\(G\equiv G_0-G_0(\ln G_0-F)\equiv G_0(1-\ln G_0+F)\pmod{x^n}\)

幂函数（弱化版）

给定多项式\(F\)，求\(G\equiv F^k\pmod{x^n}\)
想办法把\(k\)搞出来，那么\(\ln G\equiv k\ln F\pmod{x^n}\)，所以\(G\equiv e^{k\ln F}\pmod{x^n}\)
（需要保证\(a_0=[x^0]F(x)=1\)，否则需要另行处理，这个以后再提）