hdu #5730 Shell Necklace （CDQ分治+FFT）

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≤10^5. Following line is a sequence with n non-negative integer a1,a2,…,an, and ai≤10^7 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的项链有a[i]种装饰方法，问长度为n的项链有几种装饰方法
不难看出，这道题可以用dp求解，我们设f[i]表示长度为i的项链的装饰方法数，则有

f [i] = \sum j = 1 i - 1 f [j] * a [i - j]

对于这个方程，我们不能用常规的方法优化，但是不难发现，

f[j]∗a[i−j] 很像卷积的形式
考虑CDQ分治，我们可以发现，f[i]并不一定要一次算完，我们可以根据CDQ分治的思想，对于[l,r]区间，可以在计算完左半段后，用FFT计算左半段对右半段的贡献。
对于区间[l,r]，考虑多项式

S = f [l] * x 0 + f [l + 1] * x 1 + . . . + f [m i d] * x m i d - l

T = a [1] * x 0 + a [2] * x 1 + . . . + a [m i d - l + 1] * x m i d - l

则有

S∗T 的

xi−l−1 次项系数即为[l,mid]区间对i的贡献

(i∈[mid+1,r])
细节问题很多，具体看代码

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#define N 150050
#define mod 313
#define pi acos(-1.0)
using namespace std;
int R[N],f[N],a[N],n;
struct com
{
    double x,y;
    inline com operator +(com b) {com ret;ret.x=x+b.x,ret.y=y+b.y;return ret;}
    inline com operator -(com b) {com ret;ret.x=x-b.x,ret.y=y-b.y;return ret;}
    inline com operator *(com b) {com ret;ret.x=x*b.x-y*b.y,ret.y=x*b.y+y*b.x;return ret;}
}s[N*2],t[N*2];
template<class _T>inline void read(_T &x)
{
    x=0;
    char ch=getchar();
    int f=0;
    while (!isdigit(ch)) {if (ch=='-') f=1;ch=getchar();}
    while (isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    if (f) x=-x;
}
inline void fft(com a[],int n,int k)
{
    for (int i=0;i<n;i++) if (i<R[i]) swap(a[i],a[R[i]]);
    for (int i=1;i<n;i<<=1)
    {
        com w,wn,X,Y;
        wn.x=cos(pi/i),wn.y=k*sin(pi/i);
        for (int j=0;j<n;j+=(i<<1))
        {
            w.x=1,w.y=0;
            for (int _=0;_<i;_++,w=w*wn)
            {
                X=a[j+_],Y=w*a[j+_+i];
                a[j+_]=X+Y,a[j+_+i]=X-Y;
            }
        }
    }
    if (k==-1) for (int i=0;i<n;i++) a[i].x/=n;
}
inline void cdq(int l,int r)
{
    if (l==r) {f[l]=(f[l]+a[l])%mod;return;}
    int mid=(l+r)/2,len=1,ll=0;
    cdq(l,mid);
    while (len<=(r-l+1)) len<<=1,ll++;
    for (int i=0;i<len;i++) R[i]=(R[i>>1]>>1)|((i&1)<<(ll-1));
    for (int i=0;i<len;i++) s[i].x=s[i].y=t[i].x=t[i].y=0.0;
    for (int i=l;i<=mid;i++) s[i-l].x=f[i];
    for (int i=0;i<r-l+1;i++) t[i].x=a[i+1];
    fft(s,len,1),fft(t,len,1);
    for (int i=0;i<len;i++) s[i]=s[i]*t[i];
    fft(s,len,-1);
    for (int i=mid+1;i<=r;i++) f[i]=(f[i]+int(s[i-l-1].x+0.4))%mod;
    cdq(mid+1,r);
}
int main()
{
    while (1)
    {
        read(n);
        if (n==0) break;
        for (int i=1;i<=n;i++) read(a[i]),a[i]%=mod,f[i]=0;
        cdq(1,n),printf("%d\n",f[n]);
    }
}

秒客网

hdu #5730 Shell Necklace （CDQ分治+FFT）

相关文章