多项式全家桶

notice:以下均为$n$项式，最高次幂为 $n-1$。

多项式求逆

对于函数$f(x)=\sum_{i=0}^{n-1}a_ix^i$有一函数$g(x)=\sum_{i=0}^{n-1}b_ix^i$满足$f(x)*g(x)\equiv1\ (mod\ x^n)$此时称$g(x)$为$f(x)$的逆函数。

设$h(x)= g(x)\ (mod\ x^{\lceil\frac{n}{2}\rceil})$

有$h(x)*f(x)\equiv 1\ (mod\ x^{\lceil\frac{n}{2}\rceil})$

$g(x)*f(x)\equiv 1\ (mod\ x^{\lceil\frac{n}{2}\rceil})$

$g(x)-h(x)\equiv\ 0\ (mod\ x^{\lceil\frac{n}{2}\rceil})$

$(g(x)-h(x))^2\equiv\ 0\ (mod\ x^n)$

$g^2(x)-2g(x)h(x)+h^2(x)\equiv\ 0\ (mod\ x^n)$

同时乘上$f(x)$，有

$g(x)-2h(x)+f(x)h^2(x)\equiv\ 0\ (mod\ x^n)$

$g(x)=(2-f(x)h(x))h(x)\ (mod\ x^n)$

多项式ln

即$g(x)=\ln f(x)\ (mod\ x^n)$

（以下均为$mod\ x^n$）

$g’(x)=\frac{f’(x)}{f(x)}$