BJOI 2017 魔法咒语（AC自动机+动态规划+矩阵乘法）

发表于 |
字数统计: 1,803字 | 阅读时长 ≈ 8min

【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$）。

样例输入

4 2 10

boom

oo

ooh

bang

ob

mo

样例输出

14

数据规模与约定

显然分数据范围考虑。

对于前$60\%$的数据，直接将禁忌串建成AC自动机，然后在自动机上用基本词汇来转移。

令$F[i][pos]$表示当前匹配长度为$i$，且在自动机上$pos$位置的方案数，那么预处理自动机上每个位置跑每个基本词汇后到的位置，那么直接转移就行了。答案就是$\sum F[L][i]$

对于后$40\%$的数据，考虑矩阵乘法，考虑构造转移矩阵将$F[i][1]\dots F[i][tot],F[i+1][1]\dots F[i+1][tot]$转移到$F[i+1][1]\dots F[i+1][tot],F[i+2][1]\dots F[i+2][tot]$，这个跟刚才的dp是一样的，长度为1的基本词汇能从$F[i+1]\rightarrow F[i+2]$，长度为2的能从$F[i]\rightarrow F[i+2]$，左下部分直接给单位矩阵就行了。答案同样是$\sum F[L][i]$

代码：

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
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#define N 205
using namespace std;
struct ACM
{
	int tot,rt,fail[N],son[N][26],num[N];
	ACM(){tot=rt=1;}
	void Ins(char *s)
	{
		int i,p=rt,t,l=strlen(s);
		for(i=0;i<l;i++)
		{
			t=s[i]-'a';
			if(!son[p][t])son[p][t]=++tot;
			p=son[p][t];
		}
		num[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]);
				num[son[p][i]]|=num[fail[son[p][i]]];
			}
			else son[p][i]=son[fail[p]][i];
		}
	}
}Avoid;
const int mod=1e9+7;
int n,m,L,to[N][N],F[N][N],Ans[N][N];
char s1[N][N],s2[N][N];
int l1[N],l2[N],ans;
void Work1()
{
	int i,j,k,l,p;
	F[0][Avoid.rt]=1;
	for(i=0;i<L;i++)
	for(j=1;j<=Avoid.tot;j++)
	if(F[i][j])
	{
		for(k=1;k<=n;k++)
		if(to[j][k]!=-1&&i+l1[k]<=L)(F[i+l1[k]][to[j][k]]+=F[i][j])%=mod;
	}
	for(i=1;i<=Avoid.tot;i++)(ans+=F[L][i])%=mod;
	printf("%d",ans);
}
void C(int x[N][N],int y[N][N])
{
	int i,j,k,z[N][N];
	memset(z,0,sizeof(z));
	for(i=1;i<=Avoid.tot*2;i++)
	for(j=1;j<=Avoid.tot*2;j++)
	for(k=1;k<=Avoid.tot*2;k++)z[i][j]=(z[i][j]+1ll*x[i][k]*y[k][j]%mod)%mod;
	memcpy(x,z,sizeof(z));
}
void QM(int b)
{
	for(int i=1;i<=2*Avoid.tot;i++)Ans[i][i]=1;
	while(b)
	{
		if(b&1)C(Ans,F);
		b>>=1;C(F,F);
	}
	memset(F,0,sizeof(F));
	F[1][Avoid.tot+Avoid.rt]=1;
	C(F,Ans);
	for(int i=1;i<=Avoid.tot;i++)(ans+=F[1][i+Avoid.tot])%=mod;
	printf("%d",ans);
}
void Work2()
{
	int i,j,k;
	for(i=1;i<=Avoid.tot;i++)
	for(j=1;j<=n;j++)
	if(to[i][j]!=-1)
	{
		if(l1[j]==1)F[i+Avoid.tot][Avoid.tot+to[i][j]]++;
		else F[i][Avoid.tot+to[i][j]]++;
	}
	for(i=1;i<=Avoid.tot;i++)F[i+Avoid.tot][i]=1;
	QM(L);
}
main()
{
	int i,j,k,l,p;
	scanf("%d%d%d",&n,&m,&L);
	for(i=1;i<=n;i++)scanf("%s",s1[i]),l1[i]=strlen(s1[i]);
	for(i=1;i<=m;i++)scanf("%s",s2[i]),l2[i]=strlen(s2[i]);
	for(i=1;i<=m;i++)Avoid.Ins(s2[i]);
	Avoid.Build();
	for(i=1;i<=Avoid.tot;i++)
	for(j=1;j<=n;j++)
	{
		l=strlen(s1[j]);
		for(p=i,k=0;(!Avoid.num[p])&&k<l;k++)p=Avoid.son[p][s1[j][k]-'a'];
		if(Avoid.num[p])to[i][j]=-1;
		else if(k<l)to[i][j]=-1;
		else to[i][j]=p;
	}
	if(L<=100)Work1();
	else Work2();
}