HDU 5730 Shell Necklace FFT+cdq分治优化DP

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

Shell Necklace

Time Limit: 16000/8000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

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 1n105 . Following line is a sequence with n non-negative integer a1,a2,,an, and ai107 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

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
 题意:装饰一条链上的n个珠子,装饰任意连续i个珠子的方案数是a[i],每个珠子只能被装饰一次,求装饰这n个珠子的方案数的总数。
思路:很容易得出,装饰前i个珠子的方案数为dp[i]=sigma(dp[j]*a[i-j])  (0<=j<i)。很显然是一个卷积,但是dp同时出现在等号前后,需要用CDQ分治加上FFT优化。对于一个区间[l,r],我们先求出[l,mid]的答案,在求出[l,mid[对[mid+1,r]的影响。对于l端点,如果要影响到r端点,就需要卷积a[i]的长度r-mid+1。用dp[l~id]和a[1~r-mid+1]进行卷积(FFT)后取出对应位置加到dp上即可。
 

发表评论

电子邮件地址不会被公开。 必填项已用*标注