hdu 5689 NTT 母函数

短命女 2021-11-09 22:12 285阅读 0赞

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int mod=998244353;
    const int maxn=1e6+10;
    //int a[maxn];
    ll b[maxn];
    ll c[maxn];
    ll d[maxn];
    ll WWW[maxn];
    ll qpow(ll base,ll k)
    {
        ll tmp=1;
        while(k)
        {
            if(k&1) tmp=tmp*base%mod;
            base=base*base%mod;
            k>>=1;
        }
        return tmp;
    }
    void NTT(ll *a,int n,int flag)
    {
        for(int i=0,k=0;i<n;++i)
        {
            if(i>k) swap(a[i],a[k]);
            for(int j=(n>>1);(k^=j)<j;j>>=1);
        }
        for(int i=1;i<n;i<<=1)
        {
            ll wn=qpow(3, (mod-1)/(i<<1));
            if(flag==-1) wn=qpow(wn, mod-2);
            for(int j=0;j<n;j+=(i<<1))
            {
                ll w=1,x,y;
                for(int k=0;k<i;++k)
                {
                    x=a[j+k], y=1ll*w*a[j+k+i]%mod;
                    a[j+k]=(1ll*x+y)%mod, a[j+k+i]=(1ll*x-y+mod)%mod;
                    w*=wn, w%=mod;
                }
            }
        }
        if(flag==-1)
        {
            ll rev=qpow(n, mod-2);
            for(int i=0;i<n;++i) a[i]=(1ll*a[i]*rev)%mod;
        }
    }
    void make(int n,int m,ll *A,ll *B){
        int len=0;
        for(len=1;len<(n+m+1);len<<=1);
    
        NTT(A,len,1);
        NTT(B,len,1);
        for(int i=0;i<len;++i) A[i]=(1ll*A[i]*B[i])%mod;
        NTT(A,len,-1);
        for(int i=n;i<len;++i) A[i] = 0;
       // NTT(B,len,-1);
    }
    const int N=2e6+10;
    ll xx[N];
    ll yy[N];
    void inint(){
        xx[0]=1; yy[0]=1; int n=N-1;
        for(int i=1;i<=n;i++)   xx[i]=xx[i-1]*i%mod;
        yy[n]=qpow(xx[n],mod-2);
        for(int i=n-1;i>=1;i--) yy[i]=yy[i+1]*(i+1)%mod;
    }
    int CC(int n,int w){
        if(w>n) return 0;
        return 1ll*xx[n]*yy[w]%mod*yy[n-w]%mod;
    }
    int main(){
       inint(); //cout<<CC(1000000,5000)<<endl;
       int T; scanf("%d",&T);
       while(T--){
           int n,m; scanf("%d %d",&n,&m);
           for(int i=0;i<n;i++) scanf("%lld",&WWW[i]);
           int x=0,y=0,z=0;
           for(int i=1;i<=m;i++){
                int w; scanf("%d",&w);
            if(w==1) x++;
            if(w==2) y++;
            if(w==3) z++;
           }
           if(x) { for(int i=0;i<n;i++) if(i%1==0) { int t=i/1; b[i]=CC(x+t-1,t); }  }
           if(y) { for(int i=0;i<n;i++) if(i%2==0) { int t=i/2; c[i]=CC(y+t-1,t); }  }
           if(z) { for(int i=0;i<n;i++) if(i%3==0) { int t=i/3; d[i]=CC(z+t-1,t); }  }
           if(x) make(n,n,WWW,b); 
           if(y) make(n,n,WWW,c);
           if(z) make(n,n,WWW,d);  ll ans=0;
           for(int i=0;i<n;i++)  { WWW[i]=(WWW[i]%mod+mod)%mod; ans=( ans^( (i+1)*WWW[i]) );}
           printf("%lld\n",ans);
           memset(WWW,0,sizeof(WWW));
           memset(b,0,sizeof(b));
           memset(c,0,sizeof(c));
           memset(d,0,sizeof(d));
       }
       return 0;
    }

转载于:https://www.cnblogs.com/Andromeda-Galaxy/p/11232920.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211109/da28168b9ed5433fa351ef5da2a42799.png