多项式

· · 个人记录

多项式求逆

给定多项式F,求一个G使得F*G\equiv1 \pmod {x^n}

多项式的模意义是指次数大于等于n的项都当成0，考虑倍增，设有多项式 A 满足 F*A\equiv 1 \pmod {x^{\lceil{\frac{n}2}\rceil}} ，上取整的意思为了让它平方后大于等于n的项都当成0。

显然有F*G\equiv1 \pmod {x^{\lceil{\frac{n}2}\rceil}} ，根据模的定义可知。

所以有F*(G-A)\equiv 0 \pmod{x^{\lceil{\frac{n}2}\rceil}}，F不可能为0，于是(G-A)^2\equiv0 \pmod{x^n}，继续推一发，得到G^2-2AG+A^2\equiv 0 \pmod{x^n}，两边同时乘F得到G-2A+A^2F\equiv 0 \pmod{x^n}，所以推出G\equiv 2A-A^2F，只有常数项的时候求逆元即可，分治即可求出。

多项式求导和积分

求导，f'_{i-1}=a_iix^{i-1}

积分，积分是求导的逆运算，对一个多项式积分的结果表示哪个多项式求导得到的是这个多项式

## 多项式除法 给定多项式$F,G$，求两个多项式$A,B$满足$F=A*G+B$。 其中$F,G,A$的项数分别为$n,m,n-m$，要求$B$的项数小于$m

定义一种变换，F_{R(x)}=x^n F(\frac{1}x)，容易发现这种变换就是将F的系数reverse了一下。

F=A*G+B F(\frac{1}x)=A(\frac{1}x)G(\frac{1}x)+B(\frac{1}x) x^nF(\frac{1}x)=x^nA(\frac{1}x)G(\frac{1}x)+x^nB(\frac{1}x) x^nF(\frac{1}x)=x^{n-m}A(\frac{1}x)x^mG(\frac{1}x)+x^{n-m+1}x^{m-1}B(\frac{1}x) F_{R(x)}=A_{R(x)}G_{R(x)}+x^{n-m+1}B_{R(x)}

模一下x^{n-m+1}就能得到

F_{R(x)}\equiv A_{R(x)}G_{R(x)} \pmod {x^{n-m+1}} A_{R(x)}\equiv F_{R(x)}G^{-1}_{R(x)} \pmod {x^{n-m+1}}

多项式求逆即可。

多项式开根

求一个多项式F满足F^2=G，F会有两个，一般取正的。

仍然使用倍增，设F^2\equiv G\pmod {x^{2n}}，假设已经求出了A^2\equiv G\pmod {x^n}，那么有F^2-A^2\equiv0 \pmod {x^n}。

易得

(F+A)(F-A)\equiv0 \pmod {x^n} (F-A)\equiv0 \pmod {x^n} (F-A)^2\equiv0 \pmod {x^{2n}} F^2+A^2-2AF\equiv0 \pmod {x^{2n}} G+A^2-2AF\equiv0 \pmod {x^{2n}} F\equiv \frac{G+A^2}{2A}\pmod {x^{2n}}

多项式ln

求一个多项式F满足G=lnF

两边求导得到G'=ln'F F'

由ln的导数可以知道ln'F=\frac{1}F

所以G'=\frac{F'}F

于是G=\int\frac{F'}F

多项式exp

证明不会。

令G(x)\equiv e^{f(x)}\pmod {x^n},G_1(x)\equiv e^{f(x)} \pmod {x^{\frac{n}2}}

有G\equiv G_1(1-lnG_1+F) \pmod {x^n}