P3715 [BJOI2017] 魔法咒语

发表于 分类于 本文字数： 6.2k 阅读时长 ≈ 8 分钟

题意

用 个字符串拼成一个长为 的长串，长串中不能出现另外的 个字符串，求总方案数。

思路

限制条件为忌讳词语不能匹配上拼成的长串。

所以我们把忌讳词语都扔到 AC 自动机上做 dp。

令 表示基本词汇， 表示 fail 树上节点 拼接上 后会转移到的节点。

设 为当前在 fail 树上节点 ，拼成串长为 时的方案数，

如果存在一个忌讳词语以节点 结尾，那么 及其子树都不能参与转移，此时我们设其对应的 。

设 AC 自动机上有 个节点，那么转移很好写：

最后答案为 。

然后我们发现这个玩意的 高达 ，但当 较大时 。所以我们考虑点分治，对数据点。

Subtask 1

前 60pts 我们直接如上 dp。

Subtask 2

中间 20pts，， 只会对 有贡献。

艾佛森括号不再作判断语句，而是放进转移里：

中间的艾佛森括号我们提出来求和：

转移方程变成：

转移方程现在已经很像矩阵乘法了，所以我们构造转移矩阵优化 dp。

Subtask 3

最后 20pts，， 只会对 和 有贡献。

把对 的分类讨论放进转移里：

分别把两对艾佛森括号提出来：

转移方程变成了：

现在在矩阵里记录 和 两个状态就可以了。

代码

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
const int N = 55,M = 105;
const ll mod = 1e9+7;
char t[M],S[N][M];
int n,m,L,f2 = 1; ll ans;
int rt = 1,cnt = 1;
struct{
	int son[26],fail,trans[N];
	int is_ed; // is_ed 是否有一个忌讳词语以该节点结尾
	vector <int> g; // fail 树边
}tr[M];
inline void insert(){
	int now = rt;
	int len = strlen(t+1);
	for(int i=1;i<=len;++i){
		int c = t[i]-'a';
		if(!tr[now].son[c]) tr[now].son[c] = ++cnt;
		now = tr[now].son[c];
	}
	tr[now].is_ed = 1;
}
inline int get_trans(int now,int id){
	int len = strlen(S[id]+1);
	for(int i=1;i<=len;++i){
		int c = S[id][i]-'a';
		now = tr[now].son[c];
		if(tr[now].is_ed) return 0; // 不能参与转移设成 0
	}
	return now;
}
inline void get_fail(){
	queue <int> q;
	for(int i=0;i<26;++i) tr[0].son[i] = 1;
	q.push(1);
	while(!q.empty()){
		int now = q.front();
		q.pop();
		for(int i=0;i<26;++i){
			if(tr[now].son[i]){
				tr[tr[now].son[i]].fail = tr[tr[now].fail].son[i];
				q.push(tr[now].son[i]);
				// 一个节点不能转移，其子树内节点都不能参与转移
				tr[tr[now].son[i]].is_ed |= tr[tr[tr[now].son[i]].fail].is_ed; 
				tr[tr[tr[now].son[i]].fail].g.push_back(tr[now].son[i]);
			}
			else tr[now].son[i] = tr[tr[now].fail].son[i];
		}
	}
	q.push(1);
	while(!q.empty()){
		int now = q.front();
		q.pop();
		if(tr[now].is_ed) continue;
		for(int i=1;i<=n;++i) tr[now].trans[i] = get_trans(now,i);
		for(int i=tr[now].g.size()-1;i>=0;--i) q.push(tr[now].g[i]);
	}
}

inline void solve1(){ // L<=100
	ll dp[M][M];
	memset(dp,0,sizeof(dp));
	dp[1][0] = 1;
	for(int len=0;len<L;++len){
		for(int now=1;now<=cnt;++now){
			if(!dp[now][len]) continue;
			for(int i=1;i<=n;++i){
				if(tr[now].trans[i] && len+strlen(S[i]+1)<=L){
					(dp[tr[now].trans[i]][len+strlen(S[i]+1)] += dp[now][len])%=mod;
				}
			}
		}
	}
	for(int now=1;now<=cnt;++now) (ans += dp[now][L])%=mod;
}
struct Matrix{
	int row,clm;
	ll val[M<<1][M<<1];
	Matrix(){
		row = clm = 0;
		memset(val,0,sizeof(val));
	}
	Matrix(int f){
		row = clm = 0;
		memset(val,0,sizeof(val));
		if(f) for(int i=(M<<1)-1;i;--i) val[i][i] = 1;
	}
	inline Matrix operator * (const Matrix&G) const{
		Matrix res = Matrix(0);
		res.row = row; res.clm = G.clm;
		for(int k=1;k<=clm;++k){
			for(int i=1;i<=row;++i){
				for(int j=1;j<=G.clm;++j){
					(res.val[i][j] += val[i][k]*G.val[k][j])%=mod;
				}
			}
		}
		return res;
	}
	inline void operator *= (const Matrix&G){
		(*this) = (*this)*G;
	}
	friend inline Matrix quick_pow(Matrix x,int y){
		Matrix res = Matrix(1); 
		res.row = x.row; res.clm = x.clm;
		while(y){
			if(y&1) res *= x;
			x *= x;
			y >>= 1;
		}
		return res;
	}
}T,F;
inline void solve2_1(){ // |S|==1
	F.row = cnt; F.clm = 1;
	for(int i=1;i<=n;++i) F.val[tr[1].trans[i]][1]++;
	T.row = cnt; T.clm = cnt;
	for(int now=1;now<=cnt;++now){
		for(int i=1;i<=n;++i){
			T.val[tr[now].trans[i]][now]++;
		}
	}
	F = quick_pow(T,L-1)*F;
	for(int now=1;now<=cnt;++now) (ans += F.val[now][1])%=mod;
}
inline void solve2_2(){ // |S|<=2
	F.row = cnt*2; F.clm = 1;
	for(int i=1;i<=n;++i) F.val[tr[1].trans[i]][1] += (strlen(S[i]+1)==1);
	F.val[cnt+1][1] = 1; // dp[1][0] = 1
	T.row = cnt*2; T.clm = cnt*2;
	for(int now=1;now<=cnt;++now){
		for(int i=1;i<=n;++i){
			if(strlen(S[i]+1)==1) T.val[tr[now].trans[i]][now]++;
			else if(strlen(S[i]+1)==2) T.val[tr[now].trans[i]][now+cnt]++;
			T.val[now+cnt][now] = 1;
		}
	}
	F = quick_pow(T,L-1)*F;
	for(int now=1;now<=cnt;++now) (ans += F.val[now][1])%=mod;
}
int main(){

	read(n,m,L);
	for(int i=1;i<=n;++i){
		scanf("%s",S[i]+1); 
		if(strlen(S[i]+1)>1) f2 = 0; // Subtask 2 or 3
	}
	for(int i=1;i<=m;++i){
		scanf("%s",t+1);
		insert();
	}
	get_fail();
	L<=100 ? solve1() : f2 ? solve2_1() : solve2_2();	
	printf("%lld",ans);

	return 0;
}