Shell Necklace
Time Limit: 16000/8000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 534 Accepted Submission(s): 227
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.
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.
1 3 7
4
2 2 2 2
0
54
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.
题意：
一串由n颗珍珠组成的项链，连续的i个珍珠有ci种染色方式。
问n颗珍珠有多少种染色方式？
题解：
显然可知dp方程
f[i] = sigma(f[i - j] * a[j])
由于n很大，可以考虑分治fft解决。 说说这个分治fft：
如果我们需要计算出l～r的f的值。
假设我们已经计算出（l，mid）的f的值
观察方程
f[i] = sigma(f[j] * a[i - j]) 1 <= j < i
= sigma(f[j] * a[i - j]) + sigma(f[k] * a[i - k]) 1<= j <= mid, mid < k < i
所以可以分开计算f[l~mid]对f[mid+1~r]的影响。
具体过程可以看代码。
使用时记得调整一下下标。
class Complex {
public :
double real, image;
Complex(double real = ., double image = .):real(real), image(image) {}
Complex(const Complex &t):real(t.real), image(t.image) {}
Complex operator +(const Complex &t) const {
return Complex(real + t.real, image + t.image);
}
Complex operator -(const Complex &t) const {
return Complex(real - t.real, image - t.image);
}
Complex operator *(const Complex &t) const {
return Complex(real * t.real - image * t.image,
real * t.image + t.real * image);
}
};
const int N = , MOD = ;
const double PI = acos(-.);
class FFT {
/**
* 1. Need define PI
* 2. Need define class Complex
* 3. tmp is need for fft, so define a N suffice it
* 4. dig[30] -> (1 << 30) must bigger than N
* */
private :
static Complex tmp[N];
static int revNum[N], dig[];
public :
static void init(int n) {
int len = ;
for(int t = n - ; t; t >>= ) ++len;
for(int i = ; i < n; i++) {
revNum[i] = ;
for(int j = ; j < len; j++) dig[j] = ;
for(int idx = , t = i; t; t >>= ) dig[idx++] = t & ;
for(int j = ; j < len; j++)
revNum[i] = (revNum[i] << ) | dig[j];
}
}
static int rev(int x) {
return revNum[x];
}
static void fft(Complex a[], int n, int flag) {
/**
* flag = 1 -> DFT
* flag = -1 -> IDFT
* */
for(int i = ; i < n; ++i) tmp[i] = a[rev(i)];
for(int i = ; i < n; ++i) a[i] = tmp[i];
for(int i = ; i <= n; i <<= ) {
Complex wn(cos( * PI / i), flag * sin( * PI / i));
for(int k = , half = i / ; k < n; k += i) {
Complex w(., .);
for(int j = k; j < k + half; ++j) {
Complex x = a[j], y = w * a[j + half];
a[j] = x + y, a[j + half] = x - y;
w = w * wn;
}
}
}
if(flag == -) {
for(int i = ; i < n; ++i) a[i].real /= n;
}
}
static void dft(Complex a[], int n) {
fft(a, n, );
}
static void idft(Complex a[], int n) {
fft(a, n, -);
}
};
Complex FFT::tmp[N];
int FFT::revNum[N], FFT::dig[];
int n, arr[N];
int f[N];
Complex A[N], B[N];
inline void divideAndConquer(int lef, int rig) {
if(lef >= rig) return;
int mid = (lef + rig) >> ;
divideAndConquer(lef, mid);
int m;
for(m = ; m < (rig - lef + ) * ; m <<= );
for(int i = ; i < m; ++i) A[i] = B[i] = Complex();
for(int i = lef; i <= mid; ++i) A[i - lef] = Complex(f[i]);
int len = min(n, m - );
for(int i = ; i < len; ++i) B[i + ] = Complex(arr[i]);
FFT::init(m);
FFT::dft(A, m), FFT::dft(B, m);
for(int i = ; i < m; ++i) A[i] = A[i] * B[i];
FFT::idft(A, m);
for(int i = mid + ; i <= rig; ++i)
f[i] = (f[i] + ((ll)(A[i - lef].real + 0.5))) % MOD;
divideAndConquer(mid + , rig);
}
inline void solve() {
for(int i = ; i < n; ++i) arr[i] %= MOD;
for(int i = ; i <= n; ++i) f[i] = ;
f[] = ;
divideAndConquer(, n);
printf("%d\n", f[n]);
}
int main() {
while(scanf("%d", &n) == && n) {
for(int i = ; i < n; ++i) scanf("%d", &arr[i]);
solve();
}
return ;
}