51nod1172 Partial Sums V2

推一下式子发现是裸的FFT，$ans[k]=\sum_{i}\sum_{j}[i+j=k]a[i]*C_{m-1+j}^{j}$

比较坑爹的就是这个模数，于是我们上任意模数的FFT

任意模数的FFT目的就是降低卷积中的元素上界，我们设$P=\lfloor \sqrt{mod} \rfloor$，

我们将原函数中的系数变成两个$a1[i]=a[i]/P,a2[i]=a[i]%P,b1[i]=b[i]/P,b2[i]=b[i]%P$

这样我们新卷积出来的值的上限是$n*mod$，

$P^2$的系数是$a1*b1$，$P$的系数是$a1*b2+a2*b1$，$1$的系数是$a2*b2$，然后我们再分别卷积，最后统计答案即可

一开始炸精了。。改成预处理单位复数根就好了。

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #include <cmath>

 #define mod 1000000007

 #define MAXN 131072

 using namespace std;

 const double pi=acos(-1.0);

 const int P=;

 struct cmx{

     double x,y;

     cmx(){}

     cmx(double a,double b){x=a,y=b;}

     cmx operator + (cmx a){return cmx(x+a.x,y+a.y);}

     cmx operator - (cmx a){return cmx(x-a.x,y-a.y);}

     cmx operator * (cmx a){return cmx(x*a.x-y*a.y,x*a.y+y*a.x);}

     cmx operator / (double a){return cmx(x/a,y/a);}

 }A[MAXN],B[MAXN],C[MAXN],D[MAXN],E[MAXN],F[MAXN],G[MAXN],wn[MAXN],inv[MAXN];

 int n,m,N,rev[MAXN];

 long long ans[MAXN],a[MAXN],b[MAXN];

 void fft(cmx *a,int o, cmx *wn){

     register int i,j,k;

     cmx t;

     for(i=;i<N;i++)if(i<rev[i])swap(a[i],a[rev[i]]);

     for(k=;k<=N;k<<=)

         for(j=;j<N;j+=k)

             for(i=;i<(k>>);i++){

                 t=wn[N/k*i]*a[i+j+(k>>)];

                 a[i+j+(k>>)]=a[i+j]-t;

                 a[i+j]=a[i+j]+t;

             }

     if(o==-)for(i=;i<N;i++)a[i]=a[i]/N;

 }

 void FFT(long long *a,long long *b,long long *ans){

     register int i;

     for(i=;i<N;i++){

         A[i]=cmx(a[i]/P,);

         B[i]=cmx(a[i]%P,);

         C[i]=cmx(b[i]/P,);

         D[i]=cmx(b[i]%P,);

     }

     fft(A,,wn);fft(B,,wn);fft(C,,wn);fft(D,,wn);

     for(i=;i<N;i++){

         E[i]=A[i]*C[i];

         F[i]=A[i]*D[i]+B[i]*C[i];

         G[i]=B[i]*D[i];

     }

     fft(E,-,inv);fft(F,-,inv);fft(G,-,inv);

     register long long tmp;

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

         tmp=1ll*round(E[i].x);

         ans[i]=tmp%mod*P%mod*P%mod;

         tmp=1ll*round(F[i].x);

         (ans[i]+=tmp%mod*P%mod)%=mod;

         (ans[i]+=1ll*round(G[i].x))%=mod;

     }

 }

 long long qp(long long a,int b){

     long long c=;

     while(b){

         if(b&)c=c*a%mod;

         a=a*a%mod; b>>=;

     }return c;

 }

 int main(){

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

     register int i;

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

     b[]=;

     for(i=;i<n;i++)

         b[i]=1ll*b[i-]*(m-+i)%mod*qp(i,mod-)%mod;

     for(N=;N<(n<<);N<<=);

     for(i=;i<N;i++){

         if(i&)rev[i]=(rev[i>>]>>)|(N>>);

         else rev[i]=rev[i>>]>>;

     }

     for(i=;i<N;i++)

         wn[i]=cmx(cos(*pi/N*i),sin(*pi/N*i)),

         inv[i]=cmx(cos(*pi/N*i),-sin(*pi/N*i));

     FFT(a,b,ans);

     for(i=;i<n;i++)printf("%lld\n",ans[i]);

     return ;

 }

巴特西

51nod1172 Partial Sums V2

最新文章

热门文章