考虑前 \(60\) 分的做法：建出 ACAM，然后用 DP 模拟禁咒法术在 ACAM 上匹配的过程。
考虑后 \(40\) 分：发现转移的长度改变量不超过 \(2\)，考虑矩阵快速幂优化。
代码： 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
using namespace std;
const int N = 50;
const int M = 100;
const int mod = 1e9 + 7;
int n,m,l;
int len[N + 5];
char s[M + 5],t[M + 5];
int f[M + 5][M + 5];
namespace ACAM
{
struct node
{
int ch[26];
int fa,ed;
} acam[M + 5];
int las = 1,tot = 1;
inline void insert(int x,int ed)
{
if(acam[las].ch[x])
{
acam[las = acam[las].ch[x]].ed |= ed;
return ;
}
acam[las = acam[las].ch[x] = ++tot].ed |= ed;
}
int q[M + 5],head,tail;
inline void get_fail()
{
q[++tail] = 1;
for(register int i = 0;i < 26;++i)
acam[0].ch[i] = 1;
for(register int p;head < tail;)
{
p = q[++head];
for(register int i = 0;i < 26;++i)
if(acam[p].ch[i])
acam[acam[p].ch[i]].fa = acam[acam[p].fa].ch[i],q[++tail] = acam[p].ch[i],
acam[acam[p].ch[i]].ed |= acam[acam[acam[p].ch[i]].fa].ed;
else
acam[p].ch[i] = acam[acam[p].fa].ch[i];
}
}
inline int match(char *s,int len,int p)
{
if(acam[p].ed)
return 0;
for(register int i = 1;i <= len;++i)
{
p = acam[p].ch[s[i] - 'a'];
if(acam[p].ed)
return 0;
}
return p;
}
}
struct Matrix
{
int a[(M << 1) + 5][(M << 1) + 5];
inline Matrix()
{
memset(a,0,sizeof a);
}
inline Matrix(int)
{
memset(a,0,sizeof a);
for(register int i = 1;i <= (ACAM::tot << 1);++i)
a[i][i] = 1;
}
inline int *operator[](const int &x)
{
return a[x];
}
inline const int *operator[](const int &x) const
{
return a[x];
}
inline Matrix operator*(const Matrix &o) const
{
Matrix ret;
for(register int i = 1;i <= (ACAM::tot << 1);++i)
for(register int j = 1;j <= (ACAM::tot << 1);++j)
for(register int k = 1;k <= (ACAM::tot << 1);++k)
ret[i][j] = (ret[i][j] + (long long)a[i][k] * o[k][j]) % mod;
return ret;
}
} mat;
inline Matrix fpow(Matrix a,int b)
{
Matrix ret(1);
for(;b;b >>= 1)
(b & 1) && (ret = ret * a,1),a = a * a;
return ret;
}
int ans;
int main()
{
scanf("%d%d%d",&n,&m,&l);
for(register int i = 1;i <= n;++i)
scanf("%s",s + len[i - 1] + 1),len[i] = len[i - 1] + strlen(s + len[i - 1] + 1);
for(register int i = 1,len;i <= m;++i)
{
scanf("%s",t + 1),ACAM::las = 1,len = strlen(t + 1);
for(register int j = 1;j <= len;++j)
ACAM::insert(t[j] - 'a',j == len);
}
ACAM::get_fail();
if(l <= M)
{
f[0][1] = 1;
for(register int i = 0;i <= l;++i)
for(register int j = 1;j <= ACAM::tot;++j)
for(register int k = 1;k <= n;++k)
if(i + len[k] - len[k - 1] <= l)
{
int p = ACAM::match(s + len[k - 1],len[k] - len[k - 1],j);
if(p)
f[i + len[k] - len[k - 1]][p] = (f[i + len[k] - len[k - 1]][p] + f[i][j]) % mod;
}
for(register int i = 1;i <= ACAM::tot;++i)
ans = (ans + f[l][i]) % mod;
printf("%d\n",ans);
return 0;
}
for(register int i = 1;i <= n;++i)
for(register int j = 1;j <= ACAM::tot;++j)
{
int p = ACAM::match(s + len[i - 1],len[i] - len[i - 1],j);
if(p)
++mat[(len[i] - len[i - 1] == 1) * ACAM::tot + j][ACAM::tot + p];
}
for(register int i = 1;i <= ACAM::tot;++i)
mat[ACAM::tot + i][i] = 1;
mat = fpow(mat,l);
for(register int i = 1;i <= ACAM::tot;++i)
ans = (ans + mat[ACAM::tot + 1][ACAM::tot + i]) % mod;
printf("%d\n",ans);
}