2016-08-29

HDU 5730 Shell Necklace【CDQ分治+FFT】

题目链接：

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

题意：

给定连续的若干个数代表的数字，求不同的划分得到的数字乘积的和。

分析：

设$dp[i]$表示前$i$个元素的答案，则有$dp[i] = \sum_{j=1}^idp[i-j]*a[j]$，很卷积的形式，但是$dp[i-j]$会影响$dp[i]$的答案，不能直接卷，再利用$cdq$分治思想：

先得到$[L,mid]$答案，将答案对后一半的贡献转移到$[mid+1,R]$中(用FFT求卷积)，再处理$[mid+1,r]$，时间复杂度降到了$O(nlog^2n)$。

$FFT$优化的部分为：
对于$ mid \lt j \le R $，$\sum_{i=L}^{mid}a[j - i] \times dp[i] =\sum_{i=0}^{mid-L}a[j - L - i] \times dp[i-L]$
下标从$0$开始，令$x1[i] = a[i -1 ]，x2[i] = dp[i-L]$
则原式化为$\sum_{i=0}^{mid -L}x1[j-L-1-i] \times x2[i]$，一共$logn$层，每层卷积复杂度$O(nlogn)$

代码：

一写$FFT$代码就无法高亮。。。


/*************************************************************************
    > File Name: 5730.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/8/24 14:03:15
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cmath>
using namespace std;
using namespace std;
const int maxn = 1e5 + 5, mod = 313;
const double pi = acos(-1.0); 
//double转int一定要记得加0.5
struct complex
{
    double r, i;
    complex() {r = i = 0;}
    complex(double a,double b){r = a; i = b;}
    complex operator + (const complex &o) const{
        return complex(r + o.r, i + o.i);
    }
    complex operator - (const complex &o) const{
        return complex(r - o.r, i - o.i);
    }
    complex operator * (const complex &o) const{
        return complex(r * o.r - i * o.i, r * o.i + i * o.r);
    }
}x1[maxn<<2], x2[maxn<<2], A[maxn<<2]; 
int n, rev[maxn<<2];
int dp[maxn], a[maxn];
void init(int &l)
{
	int L, k, r, t;
	k = 1; L = 0;
    while(k < l) k <<= 1, ++ L;
    l = k;
    for(int i = 0; i < l; i++){
        t = i; r = 0; k = L;
        while(k--){
            r <<= 1;
            r |= t & 1; 
            t >>= 1;
        }
        rev[i] = r;
    }
}
void fft(complex *x, int l, int op)
{
    complex u, t;
    for(int i = 0; i < l; i++) A[rev[i]] = x[i];
    for(int i = 0; i < l; i++) x[i] = A[i];
    for(int k = 2; k <= l; k <<= 1){
        complex wn(cos(2 * pi/ k * op), sin(2 * pi / k * op));
        for(int i = 0; i < l; i += k){
            complex w(1, 0);
            for(int j = 0; j < k/2; j++){
                u = x[i + j]; t = w * x[i + j + k/2];
                x[i + j] = u + t; x[i + j + k/2] = u - t;
                w = w * wn;
            }
        }
    }
	//IDFT
    for(int i = 0; i < l && op == -1; i++)  x[i].r /= l;
}
void solve(int L, int R)
{
	if(L == R){
		(dp[L] += a[L]) %= mod;
		return;
	}
	int mid = L + R >> 1;
	solve(L, mid);
	int nl = R - L + 1;
	int l = nl + mid - L + 1;
	init(l);
	for(int i = 0; i < nl - 1; i++) x1[i] = complex(a[i + 1], 0);
	for(int i = nl - 1; i < l; i++) x1[i] = complex(0, 0);
	for(int i = 0; i <= mid - L; i++) x2[i] =  complex(dp[i + L], 0);
	for(int i = mid - L + 1; i < l; i++) x2[i] = complex(0, 0);
	fft(x1, l, 1); fft(x2, l, 1);
	for(int i = 0; i < l; i++) x1[i] = x1[i] * x2[i];
	fft(x1, l, -1);
	for(int i = mid + 1; i <= R; i++){
		(dp[i] += x1[i - L - 1].r + 0.5) %= mod;
	}
	solve(mid + 1, R);
}
int main(void)
{
	int n;
	while(~scanf("%d", &n) && n){
		for(int i = 1; i <= n; i++) scanf("%d", &a[i]), a[i] %= mod;
		memset(dp, 0, sizeof(dp));
		solve(1, n);
		printf("%d\n", dp[n]);
	}
	return 0;
}