HDU - 5730 ：Shell Necklace（CDQ分治+FFT）

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.

InputThere are multiple test cases(no more than 2020 cases and no more than 1 in extreme case), ended by 0.

For each test cases, the first line contains an integer nn, meaning the number of shells in this shell necklace, where 1≤n≤1051≤n≤105. Following line is a sequence with nnnon-negative integer a1,a2,…,ana1,a2,…,an, and ai≤107ai≤107 meaning the number of schemes to decorate ii continuous shells together with a declaration of love.
OutputFor each test case, print one line containing the total number of schemes module 313313(Three hundred and thirteen implies the march 13th, a special and purposeful day).Sample Input

Sample Output

14

54

Hint HDU - 5730 ：Shell Necklace（CDQ分治+FFT）

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.

见：https://blog.****.net/Maxwei_wzj/article/details/79850756

题意：一串项链是n个珠子组成，如果i个珠子连续，可以被认为是模式i，贡献是ai一串项链是n个珠子组成，如果i个珠子连续，可以被认为是模式i，贡献是ai
思路：对于一串珠子，列出DP方程，dp[i]表示长度为i的项链，所有情况的贡献和 dp[i]=∑ dp[j]*A[i-j]，复杂度O（N^2）。
观察这个式子很像卷积的形式，于是可以用cdq分治+FFT来优化一波观察这个式子很像卷积的形式，于是可以用cdq分治+FFT来优化一波。

（正确性不难证明，因为分治到Mid+1之前，dp[1]-dp[Mid]的值都已经求出来了。

#include<bits/stdc++.h>

#define ll long long

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

const int Mod=;

const double pi=acos(-1.0);

struct cp

{

    double r,i;

    cp(){}

    cp(double rr,double ii):r(rr),i(ii){}

    cp operator +(const cp&x)const{return cp(r+x.r,i+x.i);}

    cp operator -(const cp&x)const{return cp(r-x.r,i-x.i);}

    cp operator *(const cp&x)const{return cp(r*x.r-i*x.i,i*x.r+r*x.i);}

};

ll dp[maxn],A[maxn];

cp a[maxn<<],b[maxn<<],W,w,p; int R[maxn<<],n;

inline void fft(cp*c,int t)

{

    int i,j,k;

    for(i=;i<n;i++) R[i]<i?swap(c[R[i]],c[i]),:;

    for(i=;i<n;i<<=)

     for(j=,W={cos(pi/i),sin(pi/i)*t};j<n;j+=i<<)

      for(k=,w={,};k<i;k++,w=w*W)

       p=c[j+k+i]*w,c[j+k+i]=c[j+k]-p,c[j+k]=c[j+k]+p;

}

void solve(int l,int r)

{

    if(l==r) return ;

    int mid=(l+r)>> ;

    solve(l,mid);

    for(n=;n<((r-l+));n<<=);

    rep(i,,n-) R[i]=R[i>>]>>|(i&?n>>:);

    rep(i,,mid-l) a[i]=cp(dp[l+i],.);

    rep(i,mid-l+,n) a[i]=cp(,);

    rep(i,,r-l-) b[i]=cp(A[i+],.);

    rep(i,r-l,n) b[i]=cp(,);

    fft(a,); fft(b,);

    rep(i,,n-) a[i]=a[i]*b[i];

    fft(a,-);

    rep(i,mid+,r) dp[i]+=a[i-l-].r/n+0.5,dp[i]%=Mod;

    solve(mid+,r);

}

int main()

{

    int N;

    while(~scanf("%d",&N)&&N>){

        rep(i,,N) dp[i]=; dp[]=;

        rep(i,,N) scanf("%d",&A[i]),A[i]%=Mod;

        solve(,N);

        printf("%d\n",dp[N]);

    }

    return ;

}

秒客网

HDU - 5730 ：Shell Necklace（CDQ分治+FFT）

相关文章