首页 > 代码库 > HDU Shell Necklace CDQ分治+FFT

HDU Shell Necklace CDQ分治+FFT

2024-11-17 09:56:02   203人阅读

Shell Necklace

 

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 nnon-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
31 3 742 2 2 2 0
 
Sample Output
1454
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.
 

题解：

　　f[i]  = ∑ f[ n - i ] * a[i] 

　　分治FFT经典题，不作赘述

#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define ls i<<1#define rs ls | 1#define mid ((ll+rr)>>1)#define pii pair<int,int>#define MP make_pairtypedef long long LL;const long long INF = 1e18+1LL;const double pi = acos(-1.0);const int N = 3e5+10, M = 1e3+20,inf = 2e9;const LL mod = 313LL;struct Complex {    double r , i ;    Complex () {}    Complex ( double r , double i ) : r ( r ) , i ( i ) {}    Complex operator + ( const Complex& t ) const {        return Complex ( r + t.r , i + t.i ) ;    }    Complex operator - ( const Complex& t ) const {        return Complex ( r - t.r , i - t.i ) ;    }    Complex operator * ( const Complex& t ) const {        return Complex ( r * t.r - i * t.i , r * t.i + i * t.r ) ;    }} ;void FFT ( Complex y[] , int n , int rev ) {    for ( int i = 1 , j , t , k ; i < n ; ++ i ) {        for ( j = 0 , t = i , k = n >> 1 ; k ; k >>= 1 , t >>= 1 ) j = j << 1 | t & 1 ;        if ( i < j ) swap ( y[i] , y[j] ) ;    }    for ( int s = 2 , ds = 1 ; s <= n ; ds = s , s <<= 1 ) {        Complex wn = Complex ( cos ( rev * 2 * pi / s ) , sin ( rev * 2 * pi / s ) ) , w ( 1 , 0 ) , t ;        for ( int k = 0 ; k < ds ; ++ k , w = w * wn ) {            for ( int i = k ; i < n ; i += s ) {                y[i + ds] = y[i] - ( t = w * y[i + ds] ) ;                y[i] = y[i] + t ;            }        }    }    if ( rev == -1 ) for ( int i = 0 ; i < n ; ++ i ) y[i].r /= n ;}Complex y[N],s[N];LL dp[N],a[N];int n;void cdq(int ll,int rr) {     if(ll == rr) {        dp[ll] += a[ll];        dp[ll] %= mod;        return ;    }    cdq(ll,mid);    int len = 1;    while(len <= (rr-ll+2)) len<<=1;    for(int i = 0; i < len ; ++i) y[i] = Complex(0,0),s[i] = y[i];    for(int i = 0; i < len; ++i) y[i] = Complex(a[i+1],0);    for(int i = ll; i <= mid; ++i) s[i - ll] = Complex(dp[i],0);    FFT(s,len,1);FFT(y,len,1);    for(int i = 0; i < len; ++i) s[i] = y[i] * s[i];    FFT(s,len,-1);    for(int i = mid; i < rr; ++i)        dp[i+1] += LL(s[i-ll].r+0.5),dp[i] %= mod;    cdq(mid+1,rr);}int main() {    while(scanf("%d",&n)!=EOF) {        if(!n) return 0;        memset(a,0,sizeof(a));        for(int i = 1; i <= n; ++i)            scanf("%lld",&a[i]),dp[i] = 0,a[i] = a[i] % mod;        cdq(1,n);        printf("%lld\n",dp[n]);    }    return 0;}

 

HDU Shell Necklace CDQ分治+FFT


联系
我们