BJOI2017魔法咒语

发表于
字数统计: 2,120字 | 阅读时长 ≈ 10min

BJOI2017 魔法咒语

问题描述

Chandra 是一个魔法天才。

从一岁时接受火之教会洗礼之后，Chandra 就显示出对火元素无与伦比的亲和力，轻而易举地学会种种晦涩难解的法术。这也多亏 Chandra 有着常人难以企及的语言天赋，让她能轻松流利地说出咒语中那些极其拗口的魔法词汇。

直到十四岁，开始学习威力强大的禁咒法术时，Chandra 才遇到了障碍。

根据火之魔法规则，禁咒的构成单位是 N 个基本词汇。施法时只要凝聚精神力，说出一段用这些词语组成的长度恰好等于 L 的语言，就能释放威力超乎想象的火法术。过去的魔法师们总结了几种表达起来最连贯的组合方式，方便施法者以最快语速完成法术。

但具有魔法和语言双重天才的 Chandra 不满足于这几种流传下来的禁咒，因为她可以毫无困难地说出普通人几乎不可能表达的禁咒语句。然而，在实际施法时，Chandra 发现有些自创禁咒念出后不但没有预期效果，反而会使自己的精神力迅速枯竭，十分难受。

这个问题令 Chandra 万分不解。她大量阅读典籍，到处走访魔法学者，并且不顾精神折磨一次又一次尝试新咒语，希望找出问题的答案。

很多年过去了，在一次远古遗迹探险中，Chandra 意外闯进了火之神艾利克斯的不知名神殿。根据岩土特征分析，神殿应该有上万年的历史，这是极其罕见的。Chandra 小心

翼翼地四处探索，沿着魔力流动来到一间密室。她看见密室中央悬浮着一本书籍。在魔法保护下书籍状况完好。精通上古语言的 Chandra 读过此书，终于解开了多年的困惑。

禁咒法术之所以威力强大，是因为咒语借用了火之神艾利克斯的神力。这本书里记载了艾利克斯生平忌讳的 M 个词语，比如情敌的名字、讨厌的植物等等。使用禁咒法术时，如果语言中含有任何忌讳词语，就会触怒神力而失效，施法者也一并遭受惩罚。

例如，若 ”banana” 是唯一的忌讳词语，“an”、”ban”、”analysis” 是基本词汇，禁咒长度须是 11，则“bananalysis” 是无效法术，”analysisban”、”anbanbanban”是两个有效法术。注意：一个基本词汇在禁咒法术中可以出现零次、一次或多次；只要组成方式不同就认为是不同的禁咒法术，即使书写形式相同。

谜题破解，Chandra 心情大好。她决定计算一共有多少种有效的禁咒法术。

由于答案可能很大，你只需要输出答案模 1,000,000,007 的结果。

输入格式

第一行，三个正整数 N, M, L。

接下来 N 行，每行一个只含小写英文字母的字符串，表示一个基本词汇。

接下来 M 行，每行一个只含小写英文字母的字符串，表示一个忌讳词语。

输出格式

仅一行，一个整数，表示答案（模 10^9+7）。

样例输入 1

4 2 10
boom
oo
ooh
bang
ob
mo

样例输出 1

14

样例输入 2

3 1 3
a
ab
aba
aaa

样例输出 2

3

样例输入 3

3 1 14
ban
an
analysis
banana

样例输出 3

15

提示

样例解释 1】

有效的禁咒法术共有 14 种：boom/bang/oo，oo/oo/oo/oo/oo，oo/oo/ooh/ooh，

oo/ooh/oo/ooh，oo/ooh/ooh/oo，ooh/oo/oo/ooh，ooh/oo/ooh/oo，

ooh/ooh/boom，ooh/ooh/oo/oo，ooh/ooh/bang，ooh/bang/ooh，

bang/oo/oo/oo，bang/ooh/ooh，bang/bang/oo。

【样例解释 2】

有效的禁咒法术有 a/ab, ab/a, aba 共三种。注意，ab/a 和 aba 算

成两种不同的禁咒法术。

【数据规模与约定】

img

观察数据范围，明显的二合一。

对于前6组测试点，$L$很小，没有其他特殊限制。对于这一部分，我们用禁忌串建立AC自动机，问题转换为了在AC自动机上，每一次用基本词汇来跑，一共跑$L$次，求一共有多少种跑法。简单DP一下就好，预处理自动机上从每个状态跑每个基本词汇到达的状态，如果有禁忌词汇返回-1.

对于后4组测试点，$L$很大，但是有一个很强的限制：基本词汇长度不超过2.还是以自动机的角度思考问题，先考虑最简单的基本词汇长度为1的情况。这时候如果把状态之间可行的转移看成一条单向边，那么问题就转换为了从根节点开始走$L$步，一共有多少种不同的走法。这就是典型的矩阵乘法问题。

考虑基本词汇长度为2的情况。类似地，现在也想要把题目转换为矩阵乘法问题。那么对于每一个状态增加一个用来“中转”的虚拟点。如果存在一种步长为2的合法转移< u,v >，那么只需要把u对应的虚拟点入度置为1（注意不是加1，这样会导致算多），并在虚拟点与v之间加一条边即可。

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
#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<queue>
#define MAXN 333
#define ll long long
using namespace std;
const ll mod=1e9+7;

void add(int &x,int y){
	x+=y;x-=x<mod?0:mod;
}

namespace ACAM{
	int rt=1,tot=1,son[MAXN][26],fail[MAXN],mark[MAXN];
	
	void ins(char s[],int len){
		int i,p,t;
		for(i=0,p=rt;i<len;i++,p=son[p][t]){
			t=s[i]-'a';
			if(!son[p][t])son[p][t]=++tot;
		}
		mark[p]=1;
	}

	void build(){
		int i,p=rt;
		queue<int>Q;
		for(i=0;i<26;i++){
			if(son[p][i])fail[son[p][i]]=p,Q.push(son[p][i]);
			else son[p][i]=p;
		}
		while(Q.size()){
			p=Q.front();Q.pop();
			for(i=0;i<26;i++){
				if(son[p][i]){
					fail[son[p][i]]=son[fail[p]][i];
					Q.push(son[p][i]);
				}
				else son[p][i]=son[fail[p]][i];
				mark[son[p][i]]|=mark[fail[son[p][i]]];
			}
		}
	}

	int match(int st,char s[],int len){
		int p=st,i,t;
		for(i=0;i<len;i++){
			t=s[i]-'a';
			if(!mark[son[p][t]])p=son[p][t];
			else return -1;
		}
		return p;
	}
}

int N,M,L;
char bs[55][105],ban[55][105];
int Ans,lbs[55],lban[55],f[105][105],mat[105][105];
int G[205][205],Ret[205][205];

void solve1(){
	using namespace ACAM;
	int i,j,k,t;
	f[0][1]=1;
	for(i=1;i<=tot;i++)
	for(j=1;j<=N;j++)mat[i][j]=match(i,bs[j],lbs[j]);
	for(i=0;i<L;i++)
	for(j=1;j<=N;j++)if(i+lbs[j]<=L)
	for(k=1;k<=tot;k++){
		if(mark[k])continue;
		t=mat[k][j];
		if(t!=-1)add(f[i+lbs[j]][t],f[i][k]);
	}
	for(i=1;i<=tot;i++)if(!mark[i])add(Ans,f[L][i]);
	printf("%d\n",Ans);
}

int sz;

void mul(int a[205][205],int b[205][205]){
	int c[205][205]={0},i,j,k;
	for(k=1;k<=sz;k++)
	for(i=1;i<=sz;i++)
	for(j=1;j<=sz;j++)add(c[i][j],(long long)a[i][k]*b[k][j]%mod);
	for(i=1;i<=sz;i++)
	for(j=1;j<=sz;j++)a[i][j]=c[i][j];
}

void ksm(int b){
	for(int i=1;i<=sz;i++)
	for(int j=1;j<=sz;j++)Ret[i][j]=G[i][j];
	while(b){
		if(b&1)mul(Ret,G);
		b>>=1;mul(G,G);
	}
}

void solve2(){
	using namespace ACAM;
	int i,j,t;
	sz=tot*2;
	for(i=1;i<=N;i++){
		for(j=1;j<=tot;j++){
			if(mark[j])continue;
			if(lbs[i]==1){
				t=match(j,bs[i],1);
				if(t!=-1)G[j][t]++;			
			}
			else{
				t=match(j,bs[i],2);
				if(t!=-1)G[j][j+tot]=1,G[j+tot][t]++;
			}
		}
	}
	ksm(L-1);
	for(i=1;i<=tot;i++)if(!mark[i])add(Ans,Ret[1][i]);
	printf("%d\n",Ans);
}

int main(){
	int i;
	scanf("%d%d%d",&N,&M,&L);
	for(i=1;i<=N;i++){
		scanf("%s",bs[i]);
		lbs[i]=strlen(bs[i]);
	}
	for(i=1;i<=M;i++){
		scanf("%s",ban[i]);
		lban[i]=strlen(ban[i]);
	}
	for(i=1;i<=M;i++)ACAM::ins(ban[i],lban[i]);
	ACAM::build();

	if(L<=100)solve1();
	else solve2();
}