hdu Shell Necklace 5730 分治FFT

Description

Perhaps the sea‘s definition of a shell is the pearl. However, in my view, a shell necklace with n beautiful shells contains the most sincere feeling for my best lover Arrietty, but even that is not enough.

Suppose the shell necklace is a sequence of shells (not a chain end to end). Considering i continuous shells in the shell necklace, I know that there exist different schemes to decorate the i shells together with one declaration of love.

I want to decorate all the shells with some declarations of love and decorate each shell just one time. As a problem, I want to know the total number of schemes.

Input

There are multiple test cases(no more than 20 cases and no more than 1 in extreme case), ended by 0.

For each test cases, the first line contains an integer n, meaning the number of shells in this shell necklace, where 1≤n≤10⁵. Following line is a sequence with n non-negative integer a1,a2,…,an, and ai≤10⁷ meaning the number of schemes to decorate i continuous shells together with a declaration of love.

Output

For each test case, print one line containing the total number of schemes module 313(Three hundred and thirteen implies the march 13th, a special and purposeful day).

Sample Input

3
1 3 7
4
2 2 2 2
0

Sample Output

14
54

题意：就是给定长度为n，然后长度为1-n的珠子有a[i]种，问拼成长度n的方案数，每种珠子有无限个。

题解：f[i]设为拼成i的方案数，发现转移时f[i]=∑f[j]*a[i-j]+a[i] (1<=j<i)发现是个卷积的形式。

　　　如何去优化。

　　　去分治解决，设 l,mid的已经处理好了，那么，考虑l,mid对mid+1,r的贡献，

　　　对于l,mid的贡献部分做卷积运算，得出其贡献，加到mid,r中。

　　　这个过程就是CDQ的过程。

 #include<cstring>

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 #define N 200007

 #define pi acos(-1)

 #define mod 313

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(!isdigit(ch)){if(ch=='-')f=;ch=getchar();}

     while(isdigit(ch)){x=(x<<)+(x<<)+ch-'';ch=getchar();}

     return x*f;

 }

 int n,num,L;

 int a[N],rev[N],f[N];

 struct comp

 {

     double r,v;

     comp(double _r=,double _v=){r=_r;v=_v;}

     friend inline comp operator+(comp x,comp y){return comp(x.r+y.r,x.v+y.v);}

     friend inline comp operator-(comp x,comp y){return comp(x.r-y.r,x.v-y.v);}

     friend inline comp operator*(comp x,comp y){return comp(x.r*y.r-x.v*y.v,x.r*y.v+x.v*y.r);}

 }x[N],y[N];

 void FFT(comp *a,int f)

 {

     for (int i=;i<num;i++)

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

     for (int i=;i<num;i<<=)

     {

         comp wn=comp(cos(pi/i),f*sin(pi/i));

         for (int j=;j<num;j+=(i<<))

         {

             comp w=comp(,);

             for (int k=;k<i;k++,w=w*wn)

             {

                 comp x=a[j+k],y=w*a[j+k+i];

                 a[j+k]=x+y,a[j+k+i]=x-y;

             }

         }

     }

     if (f==-) for (int i=;i<num;i++) a[i].r/=num;

 }

 void CDQ(int l,int r)

 {

     if (l==r) {f[l]=(f[l]+a[l])%mod;return;}

     int mid=(l+r)>>;

     CDQ(l,mid);

     L=;for (num=;num<=(r-l+);num<<=,L++);if (L) L--;

     for (int i=;i<num;i++) rev[i]=(rev[i>>]>>)|((i&)<<L);

     for (int i=;i<num;i++) x[i]=y[i]=comp(,);

     for (int i=l;i<=mid;i++) x[i-l]=comp(f[i],);

     for (int i=;i<=r-l;i++) y[i-]=comp(a[i],);

     FFT(x,);FFT(y,);

     for (int i=;i<num;i++) x[i]=x[i]*y[i];

     FFT(x,-);

     for (int i=mid+;i<=r;i++)

         (f[i]+=x[i-l-].r+0.5)%=mod;

     CDQ(mid+,r);

 }

 int main()

 {

     while(~scanf("%d",&n)&&n)

     {

         for (int i=;i<=n;i++) a[i]=read()%mod,f[i]=;

         CDQ(,n);

         printf("%d\n",f[n]);

     }

 }

巴特西