多项式模板合集

在绞尽脑汁学习过后记下的一些笔记和代码……
我也只是半懂,\(so\) 这篇文章对初学者可能不太友好。

好的参考资料(来自 \(Miskcoo's\) \(space\) ):
从多项式乘法到快速傅里叶变换
多项式求逆元
多项式除法及求模
多项式的多点求值与快速插值
牛顿迭代法在多项式运算的应用

对于下述代码,“前置”代码:

#define P 998244353
int Pow_mod(int x,int y){
    int ret=1;
    while(y){
        if(y&1) ret=1ll*ret*x%P;
        x=1ll*x*x%P;
        y>>=1;
    }
    return ret;
}
int Plus(int x,int y) { return x+y>=P ? x+y-P : x+y; }
int Minus(int x,int y) { return x>=y ? x-y : x-y+P; }

FFT/NTT

int l,r[N],X[N];
void ntt(int *A,int ty){
    for(int i=0;i<l;i++) X[r[i]]=A[i];
    for(int i=0;i<l;i++) A[i]=X[i];
    for(int i=2;i<=l;i<<=1){
        int wn=Pow_mod(3,(P-1)/i);
        if(ty==-1) wn=Pow_mod(wn,P-2);
        for(int j=0;j<l;j+=i){
            int w=1;
            for(int k=j;k<j+i/2;k++){
                int t=1ll*w*A[k+i/2]%P;
                A[k+i/2]=Minus(A[k],t);
                A[k]=Plus(A[k],t);
                w=1ll*w*wn%P;
            }
        }
    } 
    if(ty==1) return;
    int Inv=Pow_mod(l,P-2);
    for(int i=0;i<l;i++) A[i]=1ll*A[i]*Inv%P;
}

多项式求逆

int C[N];
void inv(int *A,int *B,int x){
    if(x==1) { B[0]=Pow_mod(A[0],P-2); return; }
    inv(A,B,(x+1)>>1);
    
    l=1;
    while(l<2*x) l<<=1;
    for(int i=1;i<l;i++) r[i]=(r[i>>1]>>1)|((i&1)*(l>>1));
    
    for(int i=0;i<x;i++) C[i]=A[i];
    for(int i=x;i<l;i++) C[i]=0;
    ntt(C,1); ntt(B,1);
    for(int i=0;i<l;i++) B[i]=Minus(2ll*B[i]%P,1ll*C[i]*B[i]%P*B[i]%P);
    ntt(B,-1);
    
    for(int i=x;i<l;i++) B[i]=0;
}

多项式除法&取模

void div(int *A,int *B,int *D,int *R){ //A[N]有n项,B[N]有m项。A[x]=B[x]*D[x]+R[x]
    int Ar[N],Br[N],Dr[N];
    for(int i=0;i<n;i++) Ar[i]=A[n-i-1];
    for(int i=0;i<m;i++) Br[i]=B[m-i-1];
    inv(Br,Dr,n-m+1);
    l=1;
    while(l<2*n) l<<=1;
    for(int i=1;i<l;i++) r[i]=(r[i>>1]>>1)|((i&1)*(l>>1));
    ntt(Dr,1); ntt(Ar,1);
    for(int i=0;i<l;i++) Dr[i]=1ll*Dr[i]*Ar[i]%P;
    ntt(Dr,-1);
    for(int i=0;i<=n-m;i++) D[i]=Dr[n-m-i];
    
    for(int i=0;i<m;i++) Br[i]=B[i];
    ntt(Br,1); ntt(D,1);
    for(int i=0;i<l;i++) Br[i]=1ll*Br[i]*D[i]%P;
    ntt(Br,-1); ntt(D,-1);
    for(int i=0;i<m-1;i++) R[i]=Minus(A[i],Br[i]);
}

多项式多点求值


多项式取log


多项式exp


FWT


上一篇:HDU-6061(NTT)


下一篇:Noi2016十连测第二场-黑暗 (二项式定理/斯特林数+CDQ+NTT)