HDU 5730 FFT + 分治

题目链接

---

题意： 给定一个数组$a$，定义$a[i]$表示连续$i$个珍珠可以装饰的方案数，求n个珍珠的项链可以装饰的方案总数。

---

思路： 定义： $F[i]$：$i$个珍珠的项链可以装饰的方案总数 则很明显是一个动态规划，得： $F[0]=1$ $F[i]={\sum }_{j=1}^{i}a[j]\ast F[i-j]$

---

可见维护的时间复杂度是$O(n^2)$ 可以利用分治+FFT， 每次合并区间时，计算左半区间对右半区间的贡献。 时间复杂度：$O(n{\log }^2(n))$

---

代码：

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int N = 524300, P = 313, M = 1000; int n, i, j, k, pos[N], A[N], B[N], C[N], F[N], Q[N]; namespace FFT{ struct comp{ long double r, i;comp(long double _r=0, long double _i=0){r=_r; i=_i;} comp operator + (const comp x){return comp(r+x.r, i+x.i);} comp operator - (const comp x){return comp(r-x.r, i-x.i);} comp operator * (const comp x){return comp(r*x.r-i*x.i,r*x.i+i*x.r);} comp conj(){return comp(r, -i);} }A[N], B[N]; int a0[N], b0[N], a1[N], b1[N]; const long double pi = acos(-1.0); void FFT(comp a[], int n, int t){ for (int i = 1; i < n; i++) if (i < pos[i]) swap(a[i], a[pos[i]]); for (int d = 0; (1<<d) < n; d++) { int m = 1<<d, m2 = m<<1; long double o = pi*2/m2*t;comp _w(cos(o), sin(o)); for (int i = 0; i < n; i += m2) { comp w(1,0); for (int j = 0; j < m; j++) { comp &A = a[i+j+m], &B = a[i+j], t = w*A; A = B - t; B = B + t; w = w * _w; } } } if (t == -1) for (int i=0; i < n; i++) a[i].r /= n; } void mul(int *a, int *b, int *c){ int i, j; for (i = 0; i < k; i++) A[i] = comp(a[i], b[i]); FFT(A, k, 1); for (i = 0; i < k; i++) { j = (k-i)&(k-1); B[i] = (A[i]*A[i] - (A[j]*A[j]).conj()) * comp(0, -0.25); } FFT(B, k, -1); for (i = 0; i < k; i++) c[i] = ((long long)(B[i].r + 0.5)) % P; } void mulmod(int *a, int *b, int *c){ int i; for (i = 0; i < k; i++) a0[i] = a[i]/M, b0[i] = b[i]/M; for (mul(a0, b0, a0), i=0; i<k; i++) { c[i] = 1LL*a0[i]*M*M%P; a1[i] = a[i]%M, b1[i] = b[i] % M; } for (mul(a1, b1, a1), i=0; i<k; i++) { c[i] = (a1[i]+c[i])%P, a0[i]=(a0[i]+a1[i])%P; a1[i]=a[i]/M+a[i]%M, b1[i]=b[i]/M+b[i]%M; } for (mul(a1, b1, a1), i = 0; i < k; i++) c[i] = (1LL*M*(a1[i]-a0[i]+P)+c[i])%P; } } void Init(int len){ for (k = 1; k < len; k<<=1); j = __builtin_ctz(k) - 1; for (i = 0; i < k; i++) pos[i] = pos[i>>1]>>1|((i&1)<<j); } void CDQ(int l, int r){ if (l >= r) return; int mid = (l+r)>>1; CDQ(l, mid); Init(r-l+1); for (int i = 0; i < k; i++) A[i] = B[i] = 0; for (int i = l; i <= mid; i++) A[i-l] = F[i]; for (int i = 0; i <= r-l; i++) B[i] = Q[i]; FFT::mulmod(A, B, C); for (int i = mid+1; i <= r; i++) F[i] = (F[i] + C[i-l]) % P; CDQ(mid + 1, r); } int main(){ while (~scanf("%d", &n) && n) { for (i = 1; i <= n; i++) { int x; scanf("%d", &x); F[i] = Q[i] = x; } CDQ(0, n); printf("%d\n", (F[n]+P) % P); } return 0; }