【模板】多项式全家桶-白红宇

【模板】多项式全家桶

阅读量：5106 次

发布时间：2019-06-13

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

FFT

struct Z{    double x,y;    Z(double _x=0,double _y=0):x(_x),y(_y){};};Z operator +(Z x,Z y) {return Z(x.x+y.x,x.y+y.y);}Z operator -(Z x,Z y) {return Z(x.x-y.x,x.y-y.y);}Z operator *(Z x,Z y) {return Z(x.x*y.x-x.y*y.y,x.x*y.y+x.y*y.x);}int bit[M],n,m;Z wi[M+1],a[M],b[M];void prp(){    fo(i,0,M-1) bit[i]=(bit[i>>1]>>1)|((i&1)<<(L-1));    fo(i,0,M) wi[i]=Z(cos(2*pi*i/M),sin(2*pi*i/M));}void DFT(Z *a,int pd){    fo(i,0,M-1) if(i
    
     >1);    Z v;    for(int m=2;m<=M;half=m,m<<=1,lim>>=1)    {        fo(i,0,half-1)        {            Z w=(pd==1)?wi[i*lim]:wi[M-i*lim];            for(int j=i;j
     
      >n>>m;    fo(i,0,n) scanf("%lf",&a[i].x);    fo(i,0,m) scanf("%lf",&b[i].x);    prp();    DFT(a,1),DFT(b,1);    fo(i,0,M-1) a[i]=a[i]*b[i];    DFT(a,-1);    fo(i,0,n+m)     {        int v=(int)(a[i].x+0.5);        printf("%d ",v);    }}

NTT

inline LL md(LL x){    return(x<0)?(x+mo):((x>=mo)?x-mo:x);}void NTT(LL *a,int pd,int num){    prp(num);    fo(i,0,num-1) if(i
    
     >1,half=1;    LL v;    for(int m=2;m<=num;half=m,m<<=1,lim>>=1)    {        fo(i,0,half-1)        {            LL w=(pd==1)?wi[i*lim]:wi[num-i*lim];            for(int j=i;j

多项式求逆

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define fo(i,a,b) for(int i=a;i<=b;i++)#define fod(i,a,b) for(int i=a;i>=b;i--)#define M 262144#define mo 998244353#define LL long long#define N 100005using namespace std;LL a[M+1],b[M+1],c[M+1],wi[M+1],wg[M+1],ny2,d[M+1];int bit[M+1],n;LL ksm(LL k,LL n){ LL s=1; for(;n;n>>=1,k=k*k%mo) if(n&1) s=s*k%mo; return s;}void prp(int num,int L){ ny2=ksm(num,mo-2); fo(i,0,num) wi[i]=wg[i*(M/num)]; fo(i,0,num-1) bit[i]=(bit[i>>1]>>1)|((i&1)<<(L-1));}void NTT(LL *a,bool pd,int num){ fo(i,0,num-1) if(bit[i]
          
           >1; LL v; for(int m=2;m<=num;half=m,m<<=1,lim>>=1) { for(register int i=0;i
           
            >n; fo(i,0,n-1) scanf("%lld",&a[i]); wg[0]=1; LL c=ksm(3,(mo-1)/M); fo(i,1,M) wg[i]=wg[i-1]*c%mo; make(n,a,b); fo(i,0,n-1) printf("%lld ",b[i]);}

多项式除法（多项式取模）

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define fo(i,a,b) for(int i=a;i<=b;i++)#define fod(i,a,b) for(int i=a;i>=b;i--)#define M 524288#define mo 998244353#define LL long long#define N 100005using namespace std;LL a[M+1],b[M+1],c[M+1],wi[M+1],wg[M+1],ny2,d[M+1],r[M+1],q[M+1],l2[M+1],cf[20],f[M+1];int bit[M+1],n,m;LL ksm(LL k,LL n){ LL s=1; for(;n;n>>=1,k=k*k%mo) if(n&1) s=s*k%mo; return s;}void prp(int num){ ny2=ksm(num,mo-2); fo(i,0,num) wi[i]=wg[i*(M/num)]; fo(i,0,num-1) bit[i]=(bit[i>>1]>>1)|((i&1)<<(l2[num]-1));}void NTT(LL *a,bool pd,int num){ fo(i,0,num-1) if(bit[i]
          
           >1; LL v; for(int m=2;m<=num;half=m,m<<=1,lim>>=1) { for(register int i=0;i
           
            >1) swap(d[i],d[n-m-i]); fo(i,0,num-1) r[i]=d[i],f[i]=b[i]; num=cf[l2[n+1]]; prp(num); NTT(f,0,num),NTT(r,0,num); fo(i,0,num-1) r[i]=r[i]*f[i]%mo; NTT(r,1,num); fo(i,0,num-1) r[i]=(a[i]-r[i]+mo)%mo;}int main(){ cf[0]=1; fo(i,1,19) cf[i]=cf[i-1]*2,l2[cf[i]]=i; cin>>n>>m; fo(i,0,n) scanf("%lld",&a[i]); fo(i,0,m) scanf("%lld",&b[i]); wg[0]=1; LL c=ksm(3,(mo-1)/M); fod(i,M-1,1) if(!l2[i]) l2[i]=l2[i+1]; fo(i,1,M) wg[i]=wg[i-1]*c%mo; div(a,b,q,r); fo(i,0,n-m) printf("%lld ",q[i]); printf("\n"); fo(i,0,m-1) printf("%lld ",r[i]);}

多点求值（洛谷 P5050）

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define fo(i,a,b) for(int i=a;i<=b;++i)#define fod(i,a,b) for(int i=a;i>=b;--i)#define M 262144#define mo 998244353#define N 100005#define LL long longusing namespace std;LL a[M+1],b[M+1],c[M+1],u1[M+1],wg[M+1],u2[M+1],wi[M+1],r[M+1],q[M+1],cf[19],l2[M+1],ny[M+1],a1[20][M+1],ans[N],s1[20][M+1];int bit[M+1],n,m,fi[20][N+1],le[20][N+1],lf;LL ksm(LL k,LL n){ LL s=1; for(;n;n>>=1,k=k*k%mo) if(n&1) s=s*k%mo; return s;}void prp(int num){ fo(i,0,num) wi[i]=wg[i*(M/num)]; fo(i,0,num-1) bit[i]=(bit[i>>1]>>1)|((i&1)<<(l2[num]-1));}void NTT(LL *a,bool pd,int num){ fo(i,0,num-1) if(i
          
           >1,m=2,half=1;m<=num;half=m,lim>>=1,m<<=1) { fo(i,0,half-1) { w=(!pd)?wi[i*lim]:wi[num-i*lim]; for(int j=i;j
           
            >1) swap(d[i],d[n-m-i]); num=cf[l2[n]],prp(num); fo(i,0,m-1) r[i]=d[i],u2[i]=b[i]; fo(i,m,num-1) r[i]=d[i],u2[i]=0; NTT(r,0,num),NTT(u2,0,num); fo(i,0,num-1) r[i]=r[i]*u2[i]%mo; NTT(r,1,num); fo(i,0,m-1) r[i]=(a[i]-r[i]+mo)%mo; fo(i,m,num-1) r[i]=0;}void prd(int t,int l,int r){ if(l==r) { fi[t][l]=lf+1; le[t][l]=2; a1[t][fi[t][l]]=-b[l],a1[t][fi[t][l]+1]=1; lf+=2; return; } int mid=(l+r)>>1; prd(t+1,l,mid),prd(t+1,mid+1,r);}void doit(int t,int l,int r){ if(l==r) return; int mid=(l+r)>>1; doit(t+1,l,mid),doit(t+1,mid+1,r); fi[t][l]=fi[t+1][l]; int num=cf[l2[le[t+1][l]+le[t+1][mid+1]-1]]; prp(num); fo(i,0,num-1) { u1[i]=(i
            
             >1; div(n,le[t+1][l],s1[t],a1[t+1]+fi[t+1][l],q,s1[t+1]); query(t+1,l,mid,le[t+1][l]-1); div(n,le[t+1][mid+1],s1[t],a1[t+1]+fi[t+1][mid+1],q,s1[t+1]); query(t+1,mid+1,r,le[t+1][mid+1]-1); }}int main(){ cf[0]=1; fo(i,1,18) cf[i]=cf[i-1]<<1,l2[cf[i]]=i; fod(i,M-1,1) if(!l2[i]) l2[i]=l2[i+1]; ny[1]=1; fo(i,2,M) ny[i]=(-ny[mo%i]*(LL)(mo/i)%mo+mo)%mo; wg[0]=1; LL c=ksm(3,(mo-1)/M); fo(i,1,M) wg[i]=wg[i-1]*c%mo; cin>>n>>m; fo(i,0,n) scanf("%lld",&a[i]); fo(i,0,m-1) scanf("%lld",&b[i]); prd(0,0,m-1); doit(0,0,m-1); fo(i,0,n) s1[0][i]=a[i]; query(0,0,m-1,n+1); fo(i,0,m-1) printf("%lld\n",ans[i]);}

多项式开根（洛谷P5205）

#include 
    
     #define fo(i,a,b) for(int i=a;i<=b;++i)#define fod(i,a,b) for(int i=a;i>=b;--i)#define M 524288#define LL long long#define mo 998244353using namespace std;int l2[M+1],cf[22],n,t,bit[M+1];LL wi[M+1],wg[M+1],b[M+1],u1[M+1],u2[M+1],u3[M+1],ny[M+1],c[M+1];void prp(int num){    fo(i,0,num) bit[i]=(bit[i>>1]>>1)|((i&1)<<(l2[num]-1)),wi[i]=wg[i*(M/num)];}LL ksm(LL k,LL n){    LL s=1;    for(;n;n>>=1,k=k*k%mo) if(n&1) s=s*k%mo;    return s;}void NTT(LL *a,bool pd,int num){    fo(i,0,num-1) if(i
     
      >1,h=1,m=2;m<=num;h=m,lim>>=1,m<<=1)    {        for(register int j=0;j
      
       >n;    fo(i,0,n-1) scanf("%lld",&b[i]);    make(cf[l2[n]],b,c);    fo(i,0,n-1) printf("%lld ",c[i]);}

多项式取ln（洛谷P4725）

#include 
    
     #define fo(i,a,b) for(int i=a;i<=b;++i)#define fod(i,a,b) for(int i=a;i>=b;--i)#define mo 998244353#define LL long long#define M 262144#define N 100005#define L 18using namespace std;LL wi[M+1],wg[M+1],a[M+1],b[M+1],ny[M+1];int bit[M+1],n,cf[L+1],l2[M+1];LL ksm(LL k,LL n){    LL s=1;    for(;n;n>>=1,k=k*k%mo) if(n&1) s=s*k%mo;    return s;}void prp(int num){    fo(i,0,num)    {        bit[i]=(bit[i>>1]>>1)|((i&1)<<(l2[num]-1));        wi[i]=wg[i*(M/num)];    }    ny[num]=ksm(num,mo-2);}void NTT(LL *a,bool pd,int num){    fo(i,0,num-1) if(bit[i]
     
      >1;m<=num;h=m,m<<=1,lim>>=1)    {        for(int j=0;j
      
       >n;    cf[0]=1;    fo(i,1,L) l2[cf[i]=cf[i-1]<<1]=i;    fod(i,M-1,2) if(!l2[i]) l2[i]=l2[i+1];    ny[1]=1;    fo(i,2,M) ny[i]=(-ny[mo%i]*(LL)(mo/i)%mo+mo)%mo;     wg[0]=1,wg[1]=ksm(3,(mo-1)/M);    fo(i,2,M) wg[i]=wg[i-1]*wg[1]%mo;    fo(i,0,n-1) scanf("%lld",&a[i]);    getln(n,a,b);    fo(i,0,n-1) printf("%lld ",b[i]);}

转载于:https://www.cnblogs.com/BAJimH/p/10575044.html

你可能感兴趣的文章

[NOIP2013提高组] CODEVS 3287 火车运输(MST+LCA)

查看>>

Yii2 Lesson - 03 Forms in Yii

DataGridView的行的字体颜色变化

查看>>