并不对劲的多项式求逆-白红宇

并不对劲的多项式求逆

阅读量：5072 次

发布时间：2019-06-12

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

多项式求逆是一个很多人选择背诵全文的算法。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #include
                
                 #include
                 
                  #define rep(i,x,y) for(register int i=(x);i<=(y);++i)#define dwn(i,x,y) for(register int i=(x);i>=(y);--i)#define maxlen 100010#define maxn (maxlen<<3)#define LL long longusing namespace std;int read(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)&&ch!='-')ch=getchar(); if(ch=='-')f=-1,ch=getchar(); while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar(); return x*f;}void write(int x){ if(x==0){putchar('0'),putchar('\n');return;} int f=0;char ch[20]; if(x<0)putchar('-'),x=-x; while(x)ch[++f]=x%10+'0',x/=10; while(f)putchar(ch[f--]); putchar('\n'); return;}const LL mod=998244353;int f[maxn],g[19][maxn],tmp[maxn],n,tmpn,len,nown,nowlen,r[maxn];int mul(int x,int y){int ans=1;while(y){if(y&1)ans=(LL)ans*(LL)x%mod;x=(LL)x*(LL)x%mod,y>>=1;}return ans;}void dnt(int * a,int f){ rep(i,1,nown-1)if(i
                  
                   >1]>>1)|((i&1)<<(nowlen-1)); rep(i,(tmpn<<1),nown-1)tmp[i]=0; dnt(g[len],1),dnt(tmp,1); rep(i,0,nown-1)g[len+1][i]=((2ll-(LL)tmp[i]*(LL)g[len][i])%mod+mod)*(LL)g[len][i]%mod; dnt(g[len+1],-1); rep(i,(tmpn<<1),nown-1)g[len+1][i]=0; } rep(i,0,n-1)printf("%d ",g[len][i]); return 0;}

多项式求逆指对于函数\(F(x)\)，求\(G(x)\)，使在每一项系数模\(p\)时，有\(F(x)*G(x)\equiv1(mod\space x^n)\)

考虑倍增求\(G(x)\)

设\(F(x)=f_0+f_1*x^1+..f_{n-1}*x^{n-1}\)，\(G(x)=g_0+g_1*x^1+..g_{n-1}*x^{n-1}\)

当\(n=1\)时，有 \(F(x)*f_0^{-1}\equiv1(mod\space x^n)\)

假设已经求出 \(H(x)\) 使 \(F(x)*H(x)\equiv1(mod\space x^{\lceil\frac{n}{2}\rceil})\)(1)

设 \(H(x)=h_0+h_1*x^1+..h_{n-1}*x^{n-1}\)

因为 \(F(x)*G(x)\equiv1(mod\space x^n)\)

所以 \(F(x)*G(x)\equiv1(mod\space x^{\lceil\frac{n}{2}\rceil})\)(2)

(2)-(1)，得 \(F(x)*(G(x)-H(x))\equiv0(mod\space x^{\lceil\frac{n}{2}\rceil})\)

两边同除 \(F(x)\) ，得 \(G(x)-H(x)\equiv0(mod\space x^{\lceil\frac{n}{2}\rceil})\)

即 \(\forall i\in [0,\lceil\frac{n}{2}\rceil),g_i-h_i=0\)

那么就有 \((G(x)-H(x))^2\equiv0(mod\space x^n)\)

这是因为 \((G(x)-H(x))^2\) 第 \(i(i\in[0,n))\) 项系数为 \[\sum_{j=0}^{i}(g_j-h_j)*(g_{i-j}-h_{i-j})\]

因为 \(i<n\)，所以 \(i-j,j\) 中一定有一个小于 \(\lceil\frac{n}{2}\rceil\) ，即一定有一个为0，所以第 \(i\) 项系数为\[\sum_{j=0}^{i}0=0\]证毕

有这个结论就能得到 \(G(x)^2-2*G(x)*H(x)+H^2(x)\equiv0(mod\space x^n)\)

两边同乘 \(F(x)\)，得 \(F(x)*G(x)^2-2*F(x)*G(x)*H(x)+F(x)*H^2(x)\equiv0(mod\space x^n)\)

由 \(F(x)*G(x)\equiv1(mod\space x^n)\)，得 \(G(x)-2*H(x)+F(x)*H^2(x)\equiv0(mod\space x^n)\)

即 \(G(x)\equiv2*H(x)-F(x)*H^2(x)(mod\space x^n)\)

那么倍增+多项式乘法就可以进行多项式求逆了

转载于:https://www.cnblogs.com/xzyf/p/10031500.html

你可能感兴趣的文章