本文共 2914 字，大约阅读时间需要 9 分钟。

markdown源码https://paste.ubuntu.com/p/wyNvxb4PPQ/

假设在$\mathrm{m}\mathrm{o}\mathrm{d}{x}^n$下，多项式$A$的逆元是$F$，在$\mathrm{m}\mathrm{o}\mathrm{d}{x}^{\lceil n/2\rceil }$下，多项式$A$的逆元是$F_0$，根据多项式求逆的基本公式

（当然，正确的写法是$[x^k]F$，但是写起来不是很方便，因此修改了一下）

展开

• 对于$x<\lceil \frac{n}{2}\rceil$的情况，可以得到

  $$F(x)=2F_0(x)-\sum _{j=0}^x{F}_0(j)R(x-j)$$
  由于$x<\lceil \frac{n}{2}\rceil$，因此$R(x-j)$只有在$j=x$时值为$1$，其他情况都为$0$，因此
  $$F(x)=2F_0(x)-F_0(x)=F_0(x)$$

• 对于$x\ge \lceil \frac{n}{2}\rceil$的情况，由于$F_0$的次数为$\lceil \frac{n}{2}\rceil -1$，因此$F_0(x)$当$x\ge \lceil \frac{n}{2}\rceil$时值为$0$，

  $$F(x)=-\sum _{j=0}^x{F}_0(j)R(x-j)$$
  若$x-j<\lceil \frac{n}{2}\rceil$，则$R(x-j)=0$，因此
  $$F(x)=-\sum _{j=0}^{x-\lceil n/2\rceil }{F}_0(j)R(x-j)$$
  定义
  $$G=-F_0[\frac{R}{x^{\lceil n/2\rceil }}]x^{\lceil n/2\rceil }$$
  其中，对于一个多项式$F$，定义$[F]$为$F$舍弃$\forall k<0,x^k$与其系数，例如$[6x^{-3}+2+5x]=2+5x$。

  展开得到

  $$G(x)=-\sum _{j=0}^{n-1}{F}_0(j)R(x-j)[x-j\ge \lceil \frac{n}{2}\rceil ]$$
  即
  $$G(x)=-\sum _{j=0}^{x-\lceil n/2\rceil }{F}_0(j)R(x-j)$$
  容易发现
  $$G(x)=F(x)$$
  而$G$在求出$R$的基础上只需要求一个$\lceil \frac{n}{2}\rceil$次多项式和一个$n-\lceil \frac{n}{2}\rceil$次多项式的乘积，较为简便。

代码

inline int getinv(int *s,int len,int *res){
     if(len==1)    {
         res[0]=quickpow(s[0],mod-2);      return 0;    }  int k=(len+1)/2;  getinv(s,k,res);  for(int i=0; i

其中multi(int *a,int lena,int *b,int lenb,int *res,int k)函数代表将多项式a和多项式b乘起来并$\mathrm{m}\mathrm{o}\mathrm{d}{x}^k$保存在res数组中。

转载地址：https://blog.csdn.net/wang3312362136/article/details/86160828 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！