题目

Source

http://acm.hdu.edu.cn/showproblem.php?pid=5730

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

分析

题目大概说已知连续i（1<=i<=n）个贝壳组合成一段项链的方案数a[i]，求组合成包含n个贝壳的项链的总方案数。

• dp[i]表示组合成包含i个贝壳的项链的总方案数
• 转移：dp[i]=Σdp[i-j]*a[j]（1<=j<=i）

直接枚举转移的话时间复杂度O(n²)，是不行的。

其实这个转移方程是个比较特殊的卷积形式，可以用FFT去求，但是从1到n依次求的话时间复杂度是O(n²logn)。

而利用CQD分治，每次治的过程累加左半区间内各个已经求得dp值的状态对右半区间各个状态的贡献，这个贡献就是那个方程用FFT求即可，这样时间复杂度由主定理可知是O(nlog²n)。

这是个很经典的题目吧，虽然现在才做。。

代码

#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>using namespace std;#define INF (1<<30)#define MAXN 333333const double PI=acos(-1.0); struct Complex{	double real,imag;	Complex(double _real,double _imag):real(_real),imag(_imag){}	Complex(){}	Complex operator+(const Complex &cp) const{		return Complex(real+cp.real,imag+cp.imag);	}	Complex operator-(const Complex &cp) const{		return Complex(real-cp.real,imag-cp.imag);	}	Complex operator*(const Complex &cp) const{		return Complex(real*cp.real-imag*cp.imag,real*cp.imag+cp.real*imag);	}	void setValue(double _real=0,double _imag=0){		real=_real; imag=_imag;	}}; int len;Complex wn[MAXN],wn_anti[MAXN]; void FFT(Complex y[],int op){	for(int i=1,j=len>>1,k; i<len-1; ++i){		if(i<j) swap(y[i],y[j]);		k=len>>1;		while(j>=k){			j-=k;			k>>=1;		}		if(j<k) j+=k;	}	for(int h=2; h<=len; h<<=1){		Complex Wn=(op==1?wn[h]:wn_anti[h]);		for(int i=0; i<len; i+=h){			Complex W(1,0);			for(int j=i; j<i+(h>>1); ++j){				Complex u=y[j],t=W*y[j+(h>>1)];				y[j]=u+t;				y[j+(h>>1)]=u-t;				W=W*Wn;			}		}	}	if(op==-1){		for(int i=0; i<len; ++i) y[i].real/=len;	}}void Convolution(Complex A[],Complex B[],int n){	for(len=1; len<(n<<1); len<<=1);	for(int i=n; i<len; ++i){		A[i].setValue();		B[i].setValue();	}		FFT(A,1); FFT(B,1);	for(int i=0; i<len; ++i){		A[i]=A[i]*B[i];	}	FFT(A,-1);}int a[111111],d[111111];Complex A[MAXN],B[MAXN];void cdq(int l,int r){	if(l==r){		d[l]+=a[l];		d[l]%=313;		return;	}	int mid=l+r>>1;	cdq(l,mid);	for(int i=l; i<=mid; ++i) A[i-l].setValue(d[i]);	for(int i=0; i<=r-l; ++i) B[i].setValue(a[i]);	for(int i=mid-l+1; i<=r-l; ++i) A[i].setValue();	Convolution(A,B,r-l+1);	for(int i=mid+1; i<=r; ++i){		d[i]+=((long long)(A[i-l].real+0.5))%313;		d[i]%=313;	}		cdq(mid+1,r);}int main(){	for(int i=0; i<MAXN; ++i){		wn[i].setValue(cos(2.0*PI/i),sin(2.0*PI/i));		wn_anti[i].setValue(wn[i].real,-wn[i].imag);	}	int n;	while(~scanf("%d",&n) && n){		for(int i=1; i<=n; ++i){			scanf("%d",a+i);			a[i]%=313;		}		memset(d,0,sizeof(d));		cdq(1,n);		printf("%d\n",d[n]);	}	return 0;}

HDU5730 Shell Necklace（DP + CDQ分治 + FFT）