多项式总结及模板

• zhengchunchun 发布于
• 937 收藏

1.求逆 设要对多项式A求逆，逆为B： 求在模ceil（n/2）的逆，将原式与之相减后平方，发现可得在模n意义下也是0了，然后两边同乘A，移项即可倍增了（注意此时A也是在模当前长度意义下的）。 最后倍增形式为B'=2*B-B*B*A  （b’等于2b减b方a），边界为常数取逆元，也可发现多项式有无逆取决于常数有无逆元 2.开根 与求逆类似，先求ceil（n/2）,然后将A移到左边使等式右...