可读版题意：
给定 $n$ 个仅包含大写字母的模板串，求所有的长度为 $M$ 且仅包含大写字母的不同字符串中，有多少个包含至少一个模板串。答案对 $10007$ 取模。
原题意：
$JSOI$ 交给队员 ZYX 一个任务，编制一个称之为“文本生成器”的电脑软件：该软件的使用者是一些低幼人群，他们现在使用的是$GW$文本生成器 $v6$ 版。
该软件可以随机生成一些文章――总是生成一篇长度固定且完全随机的文章，也就是说，生成的文章中每个字节都是完全随机的。如果一篇文章中至少包含使用者们了解的一个单词，那么我们说这篇文章是可读的（我们称文章 $a$ 包含单词 $b$ ，当且仅当单词 $b$ 是文章 $a$ 的子串）。但是，即使按照这样的标准，使用者现在使用的 $GW$ 文本生成器 $v6$ 版所生成的文章也是几乎完全不可读的。 $ZYX$ 需要指出 $GW$ 文本生成器 $v6$ 生成的所有文本中可读文本的数量，以便能够成功获得 $v7$ 更新版。你能帮助吗？
链接
Luogu P4052
题解
正难则反。不如我们考虑所有长度为 $M$ 的字符串，一个模版串都不出现的情况数。
神似 GT考试 啊，只不过模版从一个变成了多个，那么我们就用AC自动机代替KMP。
状态：$dp[i][j]$ 表示在 $AC$ 自动机的第 $i$ 个节点上，还有$j$位的符合条件的子串数量。
先建立 $AC$ 自动机，补全 $Trie$ 图。
然后将所有不是 $end$ 节点且 $fail$ 指针一路指向的没有$end$节点的点的 $dp[i][0]$ 设为 $1$ 。
然后将26种情况转移即可。注意这里也不要转移上面的 $dp[i][0] = 0$ 的节点，来方便我们的处理，不用特判。
最后答案是 $dp[root][M]$ 。
这里比较有趣，我想了想能不能用矩阵快速幂。但是，这个地方的转移矩阵最大有可能到 $10000\times 10000$ ，会凉凉233。
代码
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
| #include <cstdio>
#include <cstring>
#include <queue>
#define ll long long
#define mod 10007
#define sigma_size 26
using namespace std;
const int MAXN = 7000,MAXM = 110;
struct AC_automaton{
int c[MAXN][sigma_size],f[MAXN],end[MAXN];
int root,cnt;
AC_automaton(){
root = cnt = 0;
}
void insert(char *str){
int n = strlen(str),nown = root;
for(int i = 0;i<n;i++){
if(!c[nown][str[i]-'A'])
c[nown][str[i]-'A'] = ++cnt;
nown = c[nown][str[i]-'A'];;
}
end[nown] |= 1;
}
void get_fail(){
queue<int> q;
while(!q.empty()) q.pop();
for(int i = 0;i<sigma_size;i++){
if(c[root][i]){
f[c[root][i]] = root;
q.push(c[root][i]);
}
}
while(!q.empty()){
int nown = q.front();q.pop();
for(int i = 0;i<sigma_size;i++){
if(c[nown][i]){
f[c[nown][i]] = c[f[nown]][i];
end[c[nown][i]] |= end[f[c[nown][i]]];
q.push(c[nown][i]);
}
else c[nown][i] = c[f[nown]][i];
}
}
}
};
AC_automaton AC;
int n,m;
char ch[MAXN];
void init(){
scanf("%d %d",&n,&m);
for(int i = 1;i<=n;i++){
scanf("%s",ch);
AC.insert(ch);
}
AC.get_fail();
}
void solve(){
static ll dp[MAXN][MAXM];
for(int i = 0;i<=AC.cnt;i++)
if(!AC.end[i]) dp[i][0] = 1;
for(int j = 1;j<=m;j++){
for(int i = 0;i<=AC.cnt;i++){
if(!AC.end[i]){
for(int k = 0;k<sigma_size;k++)
dp[i][j] += dp[AC.c[i][k]][j-1];
dp[i][j] %= mod;
}
}
}
int ans = 1;
for(int i = 1;i<=m;i++){
ans *= sigma_size;
ans %= mod;
}
printf("%lld\n",(ans-dp[0][m]+mod)%mod);
}
int main(){
init();
solve();
return 0;
}
|
