多项式的…

前言

反正慢慢学吧…

预计学习:多项式exp,ln,多点求值,多点插值,开根

先把网址放在这里

https://blog.csdn.net/coldef/article/details/76020530

https://www.cnblogs.com/zzqsblog/p/7923192.html

(…)http://blog.miskcoo.com/2015/05/polynomial-multipoint-eval-and-interpolation

http://www.mamicode.com/info-detail-1403144.html

填坑遥遥无期

多项式乘法

FFT与NTT然后截断后面的部分…

多项式求逆

已知$A(x)$,求B(x),使满足$A(x)B(x)\equiv 1(mod\;x^n)$

$n=1$时,$A(x)=c,B(x)=c^{-1}$

然后倍增

假设已知$A(x)B(x)\equiv 1(mod\;x^n)$,想要求$A(x)B^{‘}(x)\equiv 1(mod\;x^{2n})$

则$B^{‘}(x) \equiv 2B(x)-A(x)B(x)^2(mod\;x^{2n})$

推导1:

$$B^{‘}(x)-B(x)\equiv 0(mod\;x^n)$$

$$(B^{‘}(x)-B(x))^2\equiv B^{‘}(x)^2+B(x)^2-2B^{‘}(x)B(x) \equiv 0(mod\;x^{2n})$$

$$A(x)B^{‘}(x)^2+A(x)B(x)^2-2A(x)B^{‘}(x)B(x) \equiv 0(mod\;x^{2n})$$

$$B^{‘}(x)+A(x)B(x)^2-2B(x) \equiv 0(mod\;x^{2n})$$

$$B^{‘}(x) \equiv 2B(x)-A(x)B(x)^2(mod\;x^{2n})$$

推导2:

$$A(x)B(x)\equiv 1(mod\;x^n)$$

$$A(x)B(x)-1\equiv 0(mod\;x^n)$$

$$(A(x)B(x)-1)^2\equiv 0(mod\;x^{2n})$$

$$A(x)^2B(x)^2-2A(x)B(x)+1\equiv 0(mod\;x^{2n})$$

$$A(x)(2B(x)-A(x)B(x)^2)\equiv 1(mod\;x^{2n})$$

其实没什么区别…

多项式除法及取模

已知$A(x),B(x),deg\,A=n,deg\,B=m$

求$D(x),R(x)$,使满足$A(x)=D(x)B(x)+R(x)$,$deg\,D=n-m,deg\,R=m-1$(高次项不足补0)

记$A^R(x)=x^{deg\,A}A(\frac{1}{x})$,容易发现$A^R(x)$既是将A的系数反转的多项式

$$A(x)=D(x)B(x)+R(x)$$

$$A(\frac{1}{x})=D(\frac{1}{x})B(\frac{1}{x})+R(\frac{1}{x})$$

$$x^nA(\frac{1}{x})=x^{n-m}D(\frac{1}{x})x^mB(\frac{1}{x})+x^{n-m+1}x^{m-1}R(\frac{1}{x})$$

$$A^R(x)=D^R(x)B^R(x)+x^{n-m+1}R^R(x)$$

$$A^R(x)\equiv D^R(x)B^R(x)(mod\;x^{n-m+1})$$

$$A^R(x)B^R(x)^{-1}\equiv D^R(x)(mod\;x^{n-m+1})$$

运用多项式求逆即可计算出$D^R(x)$即可计算出$R(x)$

多项式开根

前来填坑

已知$A(x)$,求B(x),使满足$A(x)\equiv B^2(x)(mod\;x^n)​$

当n=1时,$A(x)=c,B(x)=\sqrt c$

然后倍增

假设已知$A(x)\equiv B^2(x)(mod\;x^n)$,想要求$A(x)\equiv B^{‘}(x)^2(mod\;x^{2n})$

则:$B^{‘}(x)\equiv \frac{B(x)^2+A(x)}{2B(x)}(mod\;x^{2n})$

推导:

$$B(x)^2\equiv B^{‘}(x)^2(mod\;x^{n})$$

$$B(x)^2-B^{‘}(x)^2\equiv 0(mod\;x^{n})$$

$$\left ( B(x)^2-B^{‘}(x)^2 \right )^2\equiv 0(mod\;x^{2n})$$

$$B(x)^4-2B(x)^2B^{‘}(x)^2+B^{‘}(x)^4\equiv 0(mod\;x^{2n})$$

$$B(x)^4+2B(x)^2B^{‘}(x)^2+B^{‘}(x)^4\equiv 4B(x)^2B^{‘}(x)^2(mod\;x^{2n})$$

$$\left[B(x)^2+B^{‘}(x)^2 \right]^2\equiv \left [2B(x)B^{‘}(x)\right]^2(mod\;x^{2n})$$

实际上这一步到下一步并不是一个充分条件,而是一个必要条件

也就是说只要满足了下面,就可以满足上面,这样可以保证找到一个可行解,但解不唯一

$$B(x)^2+B^{‘}(x)^2\equiv 2B(x)B^{‘}(x)(mod\;x^{2n})$$

$$B(x)^2+A(x)\equiv 2B(x)B^{‘}(x)(mod\;x^{2n})$$

$$B^{‘}(x)\equiv \frac{B(x)^2+A(x)}{2B(x)}(mod\;x^{2n})$$

 

《多项式的…》上有1条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注