频道导航

hdu 5730 Shell Necklace

2020-06-01 Bash 前端之家

前端之家收集整理的这篇文章主要介绍了hdu 5730 Shell Necklace，前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。

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

@H_404_14@ 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

@H_404_14@ 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

@H_403_139@a1,a2,…,an ,and

ai≤107 meaning the number of schemes to decorate

i continuous shells together with a declaration of love.

Output

@H_404_14@ 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

@H_404_14@

Sample Output

@H_404_14@

  
  
   
   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

@H_404_14@ HIT

Source

@H_404_14@ 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
*/