【HDU5730 2016 Multi-University Training Contest 1H】【FFT + cdq 分治】 Shell Necklace f[i]=∑f[i-j] x a[j]

Shell Necklace

Time Limit: 16000/8000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 290    Accepted Submission(s): 116

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

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

2016 Multi-University Training Contest 1

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
typedef double ld;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b<a)a = b; }
const int N = 1 << 17, Z = 313, ms63 = 0x3f3f3f3f;
const double PI = acos(-1.0);
struct Complex
{
	double r, i;
	Complex(double r = 0, double i = 0) : 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); }
}X[N], Y[N];
void FFT(Complex y[], int n, int rev)//rev == 1时为DFT，rev == -1时为IDFT
{
	for (int i = 1, j, k, t; i < n; ++i)
	{
		for (j = 0, k = n >> 1, t = i; 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(cos(rev * 2 * PI / s), sin(rev * 2 * PI / s));
		for (int k = 0; k < n; k += s)
		{
			Complex w(1, 0), t;
			for (int i = k; i < k + ds; ++i)
			{
				y[i + ds] = y[i] - (t = w * y[i + ds]);
				y[i] = y[i] + t;
				w = w * wn;
			}
		}
	}
	if (rev == -1) for (int i = 0; i < n; ++i) y[i].r /= n;
}
int n, a[N], f[N];
void cdq(int l, int r)
{
	if (l == r) { f[l] = (f[l] + a[l]) % Z; return; }
	int mid = l + r >> 1;
	cdq(l, mid);
	int len1 = mid - l + 1;
	int len2 = r - l + 1;
	int len = 1; while (len < len2) len <<= 1;//这里的数组大小应该是while(len < len1 + len2)
	for (int i = 0; i < len1; ++i) X[i] = Complex(f[l + i], 0);
	for (int i = len1; i < len; ++i) X[i] = Complex(0, 0);
	for (int i = 0; i < len2; ++i) Y[i] = Complex(a[i], 0);
	for (int i = len2; i < len; ++i) Y[i] = Complex(0, 0);
	FFT(X, len, 1);
	FFT(Y, len, 1);
	for (int i = 0; i < len; ++i) Y[i] = X[i] * Y[i];
	FFT(Y, len, -1);
	for (int i = mid + 1; i <= r; ++i)f[i] = f[i] + (int)(Y[i - l].r + 0.5) % Z;
	cdq(mid + 1, r);
}
int main()
{
	while (~scanf("%d", &n), n)
	{
		MS(f, 0);
		for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), a[i] %= Z;
		cdq(1, n);
		printf("%d\n", f[n]);
	}
	return 0;
}
/*
【trick&&吐槽】
在本题，我们做FFT多项式乘法的时候，X*Y的目标数组的长度要开多少呢？
按照正常的乘法逻辑，我们要把数组开到len1+len2.
然而，这道题我们只需要使用到len1

【题意】
有n（1e5）个数a[]，a[i]都是[1e7]范围的数。
f[1]=0;
f[i]=∑(f[i - j] * a[j]), j∈[1, i];
让你求f[n] % Z

【类型】
fft + cdq分治

【分析】
这道题我们不能做n次fft，会重复计算，最终导致TLE。
我们采取cdq分治的方式做加速。

所谓cdq分治，利用了这道题目中的——想求f[i],需要加进所有f[j，j<i]对f[i]的贡献
我们把区间分成了以下两块[l,mid] [mid+1,r]，
我们先处理[l,mid]，
然后把[l,mid]的影响向[mid+1,r]转移，
再去处理[mid+1,r]。
问题是，如何做转移呢？fft。

回归fft如何做大数相乘运算
v[0] v[1] v[2]
u[0] u[1] u[2]
我们乘出来之后变成了——
(0*0) (0*1+1*0) (0*2+1*1*2*0) (1*2+2*1) (2*2)

显然，
有一侧为f[l],f[l+1],f[l+2],f[l+3],...,f[mid-1],f[mid]
另一侧为a[0],a[1],a[2],...,a[mid-l]
我们乘起来就变成了——
(f[l] * a[0]) =不需要的数
...
(f[l] * a[mid+1-l] + f[l+1] * a[mid+1-l-1] + ...) = f[mid+1]
...

即，我们需要f[l]~f[mid]中的每个数
同时需要a[0]~a[r-l]中的每个数
然后FFT就可以得到结果

【时间复杂度&&优化】
尽管我们做了nlogn次FFT
但是事实上相当于只做了logn层长度为n的FFT
总的复杂度为O(nlognlogn)，可以无压力AC

这道题的数组我们要开多大呢？
100000的上log 1<<17即可

*/