hdu5730 Shell Necklace

列出dp方程$dp_n=\sum_{i=0}^{n-1}dp_ia_{n-i}$，发现可以用分治FFT优化。

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const double pi=acos(-1);
const int p=313,maxn=800010;
struct Complex
{double a,b;Complex operator + (const Complex &c) const{return (Complex){a+c.a,b+c.b};}Complex operator - (const Complex &c) const{return (Complex){a-c.a,b-c.b};}Complex operator * (const Complex &c) const{return (Complex){a*c.a-b*c.b,a*c.b+b*c.a};}
}f[maxn],g[maxn],w[maxn];
int a[maxn],dp[maxn],rev[maxn],n;
void fft(Complex *a,int m,int t,int flag)
{int x;Complex t1,t2;for (int i=0;i<m;i++)if (rev[i]>i) swap(a[i],a[rev[i]]);for (int i=0;i<t;i++)for (int j=0;j<m;j+=1<<(i+1)){x=0;for (int k=j;k<j+(1<<i);k++){t1=a[k];t2=a[k+(1<<i)];a[k]=t1+t2*w[x];a[k+(1<<i)]=t1-t2*w[x];x+=flag*(1<<(t-i-1));if (x<0) x+=m;}}
}
void divcon(int l,int r)
{if (l==r) return;int mid=(l+r)/2,m=1,t=0;divcon(l,mid);for (int i=0;i<=mid-l;i++) f[i]=(Complex){(double)dp[l+i],0.0};for (int i=0;i<=r-l-1;i++) g[i]=(Complex){(double)a[i+1],0.0};while (m<=2*(r-l-1)) m<<=1,t++;for (int i=mid-l+1;i<m;i++) f[i]=(Complex){
   0.0,0.0};for (int i=r-l;i<m;i++) g[i]=(Complex){
   0.0,0.0};for (int i=0;i<m;i++){rev[i]=0;for (int j=0;j<t;j++)rev[i]|=((i>>j)&1)<<(t-j-1);}for (int i=0;i<m;i++) w[i]=(Complex){
   cos(2*pi*i/m),sin(2*pi*i/m)};fft(f,m,t,1);fft(g,m,t,1);for (int i=0;i<m;i++) f[i]=f[i]*g[i];fft(f,m,t,-1);for (int i=mid+1;i<=r;i++)dp[i]=(dp[i]+int(f[i-l-1].a/m+0.5))%p;divcon(mid+1,r);
}
void solve()
{for (int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]%=p,dp[i]=0;dp[0]=1;divcon(0,n);printf("%d\n",dp[n]);
}
int main()
{//freopen("e.in","r",stdin);while (scanf("%d",&n)&&n) solve();
}