HDU - 6589 Sequence (生成函数+NTT)

题目链接

设序列a的生成函数$\large f(x)=\sum\limits_{i=0}^{n-1}a_ix^i$，则操作1,2,3分别对应将$f(x)$乘上$\Large\frac{1}{1-x},\frac{1}{1-x^2},\frac{1}{1-x^3}$，如果操作1,2,3分别进行了p1,p2,p3次，则最终序列的生成函数为$\Large\frac{f(x)}{(1-x)^{p_1}(1-x^2)^{p_2}(1-x^3)^{p_3}}$，套个二项式定理+多项式乘法+多项式逆元即可。由于题目中的模数刚好可以NTT，因此直接NTT即可。(ps:浮点数FFT取模常数太大，会TLE)

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int N=4e5+,M=1e6+,mod=;

 const int G=;

 int n,m,n2,a[N],b[][N],cnt[],fac[M],inv[M],invf[M];

 int Pow(int x,int p) {

     int ret=;

     for(; p; p>>=,x=(ll)x*x%mod)if(p&)ret=(ll)ret*x%mod;

     return ret;

 }

 int C(int n,int m) {return n<m?:(ll)fac[n]*invf[m]%mod*invf[n-m]%mod;}

 struct F_FT {

     int A[N],B[N],b[N],c[N];

     void FFT(int* a,int n,int f) {

         for(int i=,j=n>>,k; i<n-; ++i,j^=k) {

             if(i<j)swap(a[i],a[j]);

             for(k=n>>; j&k; j^=k,k>>=);

         }

         for(int k=; k<n; k<<=) {

             int gn=Pow(G,(mod-)/(k<<));

             if(f==-)gn=Pow(gn,mod-);

             for(int i=; i<n; i+=k<<) {

                 int g=;

                 for(int j=i; j<i+k; ++j,g=(ll)g*gn%mod) {

                     int x=a[j],y=(ll)g*a[j+k]%mod;

                     a[j]=((ll)x+y)%mod,a[j+k]=((ll)x-y+mod)%mod;

                 }

             }

         }

         if(!~f)for(int i=; i<n; ++i)a[i]=(ll)a[i]*inv[n]%mod;

     }

     void mul(int* a,int* b,int* c,int n) {

         for(int i=; i<n; ++i)A[i]=a[i],B[i]=b[i],A[i+n]=B[i+n]=;

         n<<=;

         FFT(A,n,),FFT(B,n,);

         for(int i=; i<n; ++i)c[i]=(ll)A[i]*B[i]%mod;

         FFT(c,n,-);

     }

     void inverse(int* a,int n) {

         for(int i=; i<n; ++i)b[i]=;

         b[]=Pow(a[],mod-);

         for(int m=; m<=n; m<<=) {

             mul(b,b,c,m),mul(a,c,c,m);

             for(int i=; i<m; ++i)b[i]=(((ll)b[i]*-c[i])%mod+mod)%mod;

         }

         for(int i=; i<n; ++i)a[i]=b[i];

     }

 } fft;

 int main() {

     fac[]=invf[]=inv[]=;

     for(int i=; i<M; ++i)inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;

     for(int i=; i<M; ++i)fac[i]=(ll)fac[i-]*i%mod,invf[i]=(ll)invf[i-]*inv[i]%mod;

     int T;

     for(scanf("%d",&T); T--;) {

         memset(cnt,,sizeof cnt);

         memset(a,,sizeof a);

         scanf("%d%d",&n,&m);

         n2=;

         for(; n2<n; n2<<=);

         for(int i=; i<n; ++i)scanf("%d",&a[i]);

         while(m--) {

             int x;

             scanf("%d",&x);

             cnt[x-]++;

         }

         for(int j=; j<; ++j) {

             for(int i=; i<n2; ++i)b[j][i]=;

             for(int i=; i*(j+)<n2; ++i)b[j][i*(j+)]=(ll)C(cnt[j],i)*(i&?mod-:)%mod;

             if(j)fft.mul(b[],b[j],b[],n2);

         }

         fft.inverse(b[],n2),fft.mul(a,b[],a,n2);

         ll ans=;

         for(int i=; i<n; ++i)ans^=(ll)a[i]*(i+);

         printf("%lld\n",ans);

     }

     return ;

 }

也可以直接利用性质$\Large\frac{1}{(1-x)^n}=\sum\limits_{i=0}^{n}C_{n-1+i}^{i}x^i$，省去了求逆元的过程。

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int N=4e5+,M=1e6+,mod=;

 const int G=;

 int n,m,n2,a[N],b[][N],c[N],cnt[],fac[M],inv[M],invf[M];

 int Pow(int x,int p) {

     int ret=;

     for(; p; p>>=,x=(ll)x*x%mod)if(p&)ret=(ll)ret*x%mod;

     return ret;

 }

 int C(int n,int m) {return n<m?:(ll)fac[n]*invf[m]%mod*invf[n-m]%mod;}

 struct F_FT {

     int A[N],B[N],c[N];

     void FFT(int* a,int n,int f) {

         for(int i=,j=n>>,k; i<n-; ++i,j^=k) {

             if(i<j)swap(a[i],a[j]);

             for(k=n>>; j&k; j^=k,k>>=);

         }

         for(int k=; k<n; k<<=) {

             int gn=Pow(G,(mod-)/(k<<));

             if(f==-)gn=Pow(gn,mod-);

             for(int i=; i<n; i+=k<<) {

                 int g=;

                 for(int j=i; j<i+k; ++j,g=(ll)g*gn%mod) {

                     int x=a[j],y=(ll)g*a[j+k]%mod;

                     a[j]=((ll)x+y)%mod,a[j+k]=((ll)x-y+mod)%mod;

                 }

             }

         }

         if(!~f)for(int i=; i<n; ++i)a[i]=(ll)a[i]*inv[n]%mod;

     }

     void mul(int* a,int* b,int* c,int n) {

         for(int i=; i<n; ++i)A[i]=a[i],B[i]=b[i],A[i+n]=B[i+n]=;

         n<<=;

         FFT(A,n,),FFT(B,n,);

         for(int i=; i<n; ++i)c[i]=(ll)A[i]*B[i]%mod;

         FFT(c,n,-);

     }

 } fft;

 int main() {

     fac[]=invf[]=inv[]=;

     for(int i=; i<M; ++i)inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;

     for(int i=; i<M; ++i)fac[i]=(ll)fac[i-]*i%mod,invf[i]=(ll)invf[i-]*inv[i]%mod;

     int T;

     for(scanf("%d",&T); T--;) {

         memset(cnt,,sizeof cnt);

         memset(a,,sizeof a);

         scanf("%d%d",&n,&m);

         n2=;

         for(; n2<n; n2<<=);

         for(int i=; i<n; ++i)scanf("%d",&a[i]);

         while(m--) {

             int x;

             scanf("%d",&x);

             cnt[x-]++;

         }

         for(int j=; j<; ++j) {

             for(int i=; i<n2; ++i)b[j][i]=;

             if(cnt[j]==)b[j][]=;

             else for(int i=; i*(j+)<n2; ++i)b[j][i*(j+)]=C(cnt[j]-+i,i);

             if(j)fft.mul(b[],b[j],b[],n2);

         }

         fft.mul(a,b[],a,n2);

         ll ans=;

         for(int i=; i<n; ++i)ans^=(ll)a[i]*(i+);

         printf("%lld\n",ans);

     }

     return ;

 }

巴特西

HDU - 6589 Sequence (生成函数+NTT)

最新文章

热门文章