rockdu
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.
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.
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 54Hint 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
Recommend
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<complex>
#define LL long long
using namespace std;
const double Pi = acos(-1);
const int maxn = 2e5 + 5;
const int mod = 313;
typedef complex<double> E;
namespace Poly {
int R[maxn << 1], mx2, len;
int init(int n) {
for(mx2 = 0, len = 1; len < n; ++mx2, len <<= 1) ;
for(register int i = 0; i < len; ++i)
R[i] = (R[i >> 1] >> 1) | ((i & 1) << (mx2 - 1));
return len;
}
void FFT(E * a, int type) {
for(register int i = 0; i < len; ++i)
if(i < R[i]) swap(a[i], a[R[i]]);
for(register int i = 1; i < len; i <<= 1) {
E Wn(cos(Pi / i), sin(Pi * type / i));
for(register int j = 0, p = i << 1; j < len; j += p) {
E w(1, 0);
for(register int k = 0; k < i; ++k, w = w * Wn) {
E x = a[j + k], y = w * a[j + i + k];
a[j + k] = (x + y), a[j + i + k] = (x - y);
}
}
}
}
void mul(E * a, E * b, int l) {
FFT(a, 1), FFT(b, 1);
for(register int i = 0; i < len; ++i)
a[i] = a[i] * b[i];
FFT(a, -1);
for(register int i = 0; i < len; ++i) a[i] /= len;
}
}
int n;
int a[maxn << 1], dp[maxn << 1];
E dp_tmp[maxn << 1], a_tmp[maxn << 1];
void cdq(int l, int r) {
int mid = l + r >> 1, ln;
if(l == r) return;
cdq(l, mid);
ln = Poly::init(r - l + 1);
for(register int i = 0; i <= ln; ++i)
a_tmp[i] = dp_tmp[i] = E(0, 0);
for(register int i = l; i <= mid; ++i)
dp_tmp[i - l] = dp[i];
for(register int i = l; i <= r; ++i)
a_tmp[i - l] = a[i - l];
Poly::mul(dp_tmp, a_tmp, r - l + 1);
for(register int i = mid + 1; i <= r; ++i)
(dp[i] += (LL)floor(dp_tmp[i - l - 1].real() + 0.5) % mod) %= mod;
cdq(mid + 1, r);
}
int main() {
while(1) {
scanf("%d", &n), dp[0] = 1;
if(!n) break;
for(register int i = 1; i <= n; ++i) dp[i] = 0;
for(register int i = 0; i < n; ++i)
scanf("%d", &a[i]), a[i] %= mod;
cdq(0, n), printf("%d\n", dp[n]);
}
return 0;
}
没有帐号? 立即注册