ztr的多项式板子

cwy posted @ 2018年3月15日 17:05 in 板子 , 63 阅读
namespace poly{
    struct AwD{int x;AwD(){x=0;}AwD(int _x){x=_x;}};
    AwD operator+(AwD a,AwD b){return (AwD){(a.x+b.x)%mo};}
    AwD operator-(AwD a,AwD b){return (AwD){(a.x-b.x+mo)%mo};}
    AwD operator*(AwD a,AwD b){return (AwD){(int)(1LL*a.x*b.x%mo)};}
    AwD operator^(AwD a,int b){if(!b) return (AwD){1};AwD temp=a^(b>>1);temp=temp*temp;if(b&1) temp=temp*a;return temp;}
    AwD operator/(AwD a,AwD b){return a*(b^(mo-2));}
    const AwD root=(AwD){3};
    void ntt(AwD*a,int n,int d){
        int i,j,k;
        AwD w,t,u,v;
        for(i=(n>>1),j=1;j<n;j++){
            if(i<j) t=a[i],a[i]=a[j],a[j]=t;
            for(k=(n>>1);i&k;i^=k,k>>=1);i^=k;
        }
        for(k=2;k<=n;k<<=1){
            w=root^((mo-1)/k*(k-d));
            for(i=0;i<n;i+=k){
                t=(AwD){1};
                for(j=i;j<i+(k>>1);j++){
                    u=a[j];v=t*a[j+(k>>1)];
                    a[j]=u+v;a[j+(k>>1)]=u-v;t=t*w;
                }
            }
        }
    }
    AwD a[N],b[N];
    void print(AwD*a,int l){
        for(int i=0;i<l;i++) printf("%d ",a[i].x);
        printf("\n");
    }
    void plus(AwD*_a,AwD*_b,int l,AwD*c){
        for(int i=0;i<l;i++) a[i]=_a[i],b[i]=_b[i];
        for(int i=0;i<l;i++) c[i]=a[i]+b[i];
    }
    void subt(AwD*_a,AwD*_b,int l,AwD*c){
        for(int i=0;i<l;i++) a[i]=_a[i],b[i]=_b[i];
        for(int i=0;i<l;i++) c[i]=a[i]-b[i];
    }
    void mult(AwD*_a,AwD b,int l,AwD*c){
        for(int i=0;i<l;i++) a[i]=_a[i];
        for(int i=0;i<l;i++) c[i]=a[i]*b;
    }
    void mult(AwD*_a,AwD*_b,int l,AwD*c){
        for(int i=0;i<l;i++) a[i]=_a[i],b[i]=_b[i];
        ntt(a,l,1);ntt(b,l,1);
        for(int i=0;i<l;i++) c[i]=a[i]*b[i];
        ntt(c,l,-1);
        AwD tmp=1/(AwD){l};
        for(int i=0;i<l;i++) c[i]=c[i]*tmp;
    }
    AwD a1[N],aa[N],tmp[N];
    void inv(AwD*_a,int l,AwD*b){   
        for(int i=0;i<l;i++) a1[i]=_a[i];
        for(int i=0;i<l;i++) b[i]=i?(AwD){0}:a1[i]^(mo-2);
        for(int l0=2;l0<=l;l0<<=1){
            mult(b,(AwD){2},l0>>1,tmp);
            mult(b,b,l0,b);
            for(int i=0;i<(l0<<1);i++) aa[i]=i<l0?a1[i]:(AwD){0};
            mult(aa,b,l0<<1,b);
            for(int i=l0;i<(l0<<1);i++) b[i]=(AwD){0};
            subt(tmp,b,l0,b);
        }
    }
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter