NKOJ 3933 贝壳串（CDQ分治+FFT）

发表于 |
字数统计: 731字 | 阅读时长 ≈ 4min

P3933贝壳串

问题描述

海边市场有长度分别为1到n的贝壳串出售，其中长度为i的贝壳串有a[i]种，每种贝壳串有无限个，问用这些贝壳串链接成长度为n的串有多少种方案?

输入格式

第一行，一整数n，
第二行，n个整数ai表示长度为i的贝壳串的种类数
(n<=10^5,0<=ai<=10^7)

输出格式

输出方案数，结果模313

样例输入 1

3
1 3 7

样例输出 1

14

样例输入 2

4
2 2 2 2

样例输出 2

54

dp方程比较显然，令$F[i]$表示组成长度为i的串的方案数，那么$F[i]=\sum_{k=0}^{i}A[k]\times F[i-k]$
直接递推是$n^2$的，但是我们注意到这个转移式子是一个卷积，那么可以用$FFT$来加速，但直接$FFT$显然非常不优秀，需要用到$CDQ$来解决。

假设要算$F[l]-F[r]$的dp值，那么可以先处理出$F[l]-F[mid]$的dp值，然后做一个卷积算出$F[l]-F[mid]$对$F[mid+1]-F[r]$的贡献，这里用$FFT$处理，然后递归计算$F[mid+1]-F[r]$的dp值。

由于每次做$FFT$的长度是和区间长度相关的，因此总时间复杂度$O(n\log ^2n)$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<complex>
#define N 500000
using namespace std;
const int mod=313;
const double pi=4.0*atan(1.0);
int F[N],a[N];
complex<double>A[N],B[N],C[N],D[N],wi[N];
void FFT(complex<double>W[],int n,int ty)
{
	int i,j,k,m;
	complex<double>t0,t1;
	for(i=j=0;i<n;i++)
	{
		if(i<j)swap(W[i],W[j]);
		for(k=n>>1;(j^=k)<k;k>>=1);
	}
	wi[0]=1;
	for(m=1;m<n;m<<=1)
	{
		t0=exp(complex<double>(0,ty*pi/m));
		for(i=1;i<m;i++)wi[i]=wi[i-1]*t0;
		for(k=0;k<n;k+=m<<1)
		for(i=k;i<k+m;i++)
		{
			t0=W[i];
			t1=W[i+m]*wi[i-k];
			W[i]=t0+t1;
			W[i+m]=t0-t1;
		}
	}
	if(ty==1)return;t0=1.0/n;
	for(i=0;i<n;i++)W[i]*=t0;
}
void CDQ(int l,int r)
{
	int n=1,i,j,k,mid=l+r>>1,l1,l2;
	if(l==r)return;
	CDQ(l,mid);
	l1=mid-l+1;l2=r-mid;
	while(n<=l1+l2)n<<=1;
	fill(A,A+n+n,0);
	fill(B,B+n+n,0);
	for(i=l;i<=mid;i++)A[i-l]=F[i];
	for(i=0;i<=r-l;i++)B[i]=a[i];
	FFT(A,n,1);FFT(B,n,1);
	for(i=0;i<n;i++)A[i]=A[i]*B[i];
	FFT(A,n,-1);
	for(i=mid+1;i<=r;i++)F[i]+=floor(A[i-l].real()+0.5),F[i]%=mod;
	CDQ(mid+1,r);
}
int main()
{
	int i,x,n;
	scanf("%d",&n);F[0]=1;
	for(i=1;i<=n;i++)scanf("%d",&a[i]),a[i]%=mod;
	CDQ(0,n);
	printf("%d",(F[n]+mod)%mod);
}