Shell Necklace

Time Limit: 16000/8000 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1110Accepted Submission(s): 471

Problem 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≤105 . Following line is a sequence with

n non-negative integer

a1,a2,…,an ,and

ai≤107 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

Sample Output

  
  
   
   14
54

   
    
     
     Hint 
     
     For the first test case in Sample Input,the Figure 1 provides all schemes about it. The total number of schemes is 1 + 3 + 3 + 7 = 14.

Author

HIT

Source

2016 Multi-University Training Contest 1

【分析】

分治FFT

dp[i]=Σdp[j]*a[i-j]

如果朴素转移需要O(n^2)

考虑分治

发现是一个卷积的形式

处理出来[l,mid]里的dp值后做卷积，统计[l,mid]对[mid+1,r]的贡献。

复杂度O(n log^2 n)

还卡空间2333

【代码】

//hdu 5730 Shell Necklace
#include<bits/stdc++.h>
#define pi acos(-1)
#define ll long long
#define M(a) memset(a,sizeof a)
#define fo(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
const int mxn=333333;
const int mod=313;
int N,L,n,m;
int aaa[mxn];
int R[21][mxn];
int dp[mxn];
struct E
{
    double r,f;
    E (double _r,double _f) {r=_r,f=_f;}
    E () {}
    E operator + (E u) {return E(r+u.r,f+u.f);}
    E operator - (E u) {return E(r-u.r,f-u.f);}
    E operator * (E u) {return E(r*u.r-f*u.f,r*u.f+f*u.r);}
    E operator / (int u) {return E(r/u,f/u);}
}a[400005],b[400005],c[400005];
inline void FFT(E *a,int f)
{
    fo(i,n-1) if(i<R[L][i]) swap(a[i],a[R[L][i]]);
    for(int i=1;i<n;i<<=1)
    {
        E wn(cos(pi/i),f*sin(pi/i));
        for(int j=0;j<n;j+=(i<<1))
        {
            E w(1,0);
            for(int k=0;k<i;k++,w=w*wn)
            {
                E x=a[j+k],y=w*a[j+k+i];
                a[j+k]=x+y,a[j+k+i]=x-y;
            }
        }
    }
    if(f==-1) fo(i,n-1) a[i]=a[i]/n;
}
inline void Dirich(E *a,E *b)
{
	m=n+n;L=0;
	for(n=1;n<=m;n<<=1) L++;
	FFT(a,1),FFT(b,1);
	fo(i,n) a[i]=a[i]*b[i];
	FFT(a,-1);
}
inline void CDQ(int l,int r)
{
	if(l==r)
	{
		dp[l]=(dp[l]+aaa[l])%mod;
		return;
	}
	int mid=l+r>>1;
	CDQ(l,mid);
	
	n=r-l;
	fo(i,4*n) a[i]=b[i]=E(0,0);
	fo(i,l,mid) a[i-l].r=dp[i];
	fo(i,r-l) b[i].r=aaa[i];
	Dirich(a,b);
	fo(i,mid+1,r) dp[i]=(dp[i]+(ll)(a[i-l].r+0.5)%mod)%mod;
	
	CDQ(mid+1,r);
}
int main()
{
	fo(k,1,20) fo(i,mxn-1)
	  R[k][i]=(R[k][i>>1]>>1)|((i&1)<<(k-1));
	while(scanf("%d",&N) && N)
	{
		fo(i,N) scanf("%d",&aaa[i]);
		fo(i,N) aaa[i]%=mod;
		memset(dp,sizeof dp);
		CDQ(1,N);
		printf("%d\n",(dp[N]+mod)%mod);
	}
	return 0;
}
/*
3
1 3 7
4
2 2 2 2
0
*/

hdu 5730 Shell Necklace

Shell Necklace

猜你在找的Bash相关文章