题意：
给出连续的1-n个珠子的涂色方法 a[i](1<=i<=n)， 问长度为n的珠链共有多少种涂色方案
分析：
可以得到DP方程： DP[n] = ∑(i=1,n) (DP[n-i]*a[i]).
该方程为卷积形式，故 CDQ + FFT
CDQ： 将 [l,r] 二分， 先得到[l,mid]的答案，再更新[l,mid]对[mid+1,r]的贡献.
对任意 DP[j](mid+1 <= j <= r), [l,mid] 对其贡献为 ∑(i=l,mid) (DP[i]*a[j - i]) , 即多项式 DP 与 a 相乘后次数为j项.
FFT： 优化多项式相乘.
（1 和 l 看不清的也就这破博客园了，代码还是粘下来的好，= =）
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const double PI = * atan(1.0);
const int MAXN = ;
const int MOD = ;
struct Complex
{
double x, y;
Complex(double xx = 0.0, double yy = 0.0) : x(xx), y(yy) {}
Complex operator - (const Complex &b) const
{
return Complex(x - b.x, y - b.y);
}
Complex operator + (const Complex &b) const
{
return Complex(x + b.x, y + b.y);
}
Complex operator * (const Complex &b) const
{
return Complex(x*b.x - y*b.y, x*b.y + y*b.x);
}
};
void Change(Complex y[], int len)
{
int i, j, k;
for (i = , j = len/; i < len-; i++)
{
if (i < j) swap(y[i], y[j]);
k = len / ;
while (j >= k)
{
j -= k;
k /= ;
}
if (j < k) j += k;
}
}
void FFT(Complex y[], int len,int on)
{
Change(y, len);
for (int h = ; h <= len; h <<= )
{
Complex wn( cos(-on**PI/h), sin(-on**PI/h) );
for (int j = ; j < len; j +=h)
{
Complex w(, );
for (int k = j; k < j + h/; k++)
{
Complex u = y[k];
Complex t = w * y[k + h/];
y[k] = u + t;
y[k + h/] = u - t;
w = w * wn;
}
}
}
if (on == -)
for (int i = ; i < len; i++)
y[i].x /= len;
}
int t, n;
Complex x[MAXN], y[MAXN];
int a[MAXN/], dp[MAXN/];
void CDQ(int l, int r)
{
if (l == r) { dp[l] = (dp[l] + a[l]) % MOD; return; }
int mid = (l + r) >> ;
CDQ(l, mid);//处理前半段
int len = , len1 = mid - l + , len2 = r - l + ;
while(len < len2) len <<= ;
for (int i = ; i < len1; i++) x[i] = Complex(dp[i + l], );
for (int i = len1; i < len; i++) x[i] = Complex(, );
for (int i = ; i < len2; i++) y[i] = Complex(a[i], );
for (int i = len2; i < len; i++) y[i] = Complex(, );
FFT(x, len, );
FFT(y, len, );
for (int i = ; i < len; i++) x[i] = x[i] *y[i];
FFT(x, len, -);
for (int i = mid+; i <= r; i++)//更新贡献
{
dp[i] = (int)(dp[i] + x[i - l].x + 0.5) %MOD;
}
CDQ(mid + , r);//处理后半段
}
int main()
{
while(~scanf("%d",&n) && n)
{
for (int i = ; i <= n; i++)
{
scanf("%d",&a[i]);
a[i] %= MOD;
dp[i] = ;
}
CDQ(, n);
printf("%d\n", dp[n]);
}
}