A 题面
JSOI 交给队员 ZYX 一个任务，编制一个称之为“文本生成器”的电脑软件：该软件的使用者是一些低幼人群，他们现在使用的是 GW 文本生成器 v6 版。
该软件可以随机生成一些文章——总是生成一篇长度固定且完全随机的文章。 也就是说，生成的文章中每个字符都是完全随机的。如果一篇文章中至少包含使用者们了解的一个单词，那么我们说这篇文章是可读的（我们称文章 \(s\) 包含单词 \(t\)，当且仅当单词 \(t\) 是文章 \(s\) 的子串）。但是，即使按照这样的标准，使用者现在使用的 GW 文本生成器 v6 版所生成的文章也是几乎完全不可读的。ZYX 需要指出 GW 文本生成器 v6 生成的所有文本中，可读文本的数量，以便能够成功获得 v7 更新版。你能帮助他吗？
答案对 \(10^4+7\) 取模。
输入格式
第一行有两个整数，分别表示使用者了解的单词总数 \(n\) 和生成的文章长度 \(m\)。
接下来 \(n\) 行，每行一个字符串 \(s_i\)，表示一个使用者了解的单词。
输出格式
输出一行一个整数表示答案对 \(10^4 + 7\) 取模的结果。
样例
输入：
2 2
A
B
输出：
100
数据规模
对于 $100% $ 的测试点，保证：
- \(1\leq n\leq 60 , 1\leq m\leq 100\)
- \(1\leq |s_i|\leq 100\)
- \(s_i\) 中只含大写英文字母
B 解题
简化题意： 给定一些模式串，求长度为 \(m\) 的所有文本串的个数，且该文本串至少包括一个模式串，答案对 \(10007\) 取模。
彩笔wyb开始考虑直接求文本串数量：暴力是怎么做呢...嗯...枚举 \(m\) 个字符 ，组合数学？容斥原理？@#￥%……&*，等等，容斥？
于是 发现答案可以是所有串的个数减去不包含可读串的串的个数。
所有串的个数十分明显，就是 \(26^m\) ，接下来的问题是求不可读串个数
拆分问题：假设我们只有一个单词，怎么做？
我们可以对单词做一个 KMP ，设 \(F[i,j]\) 为已构成长度为 \(i\) ,单词匹配到位置 \(j\) 的,且没有一次匹配完全的方案数。显然,转移方程是:
\(F[i,j] \to F[i+1,j\text{或者其FAIL链的某个位置}+1]\)
此时，最后答案为 \(26^m-\max(F[m,i]|i\in[1,|\text S|])\)
回到问题：多个单词
我们知道 AC 自动机可以理解为 KMP 算法的扩大版，于是正解思路已出：AC自动机+DP
令 \(dp[i][j]\) 表示构成的文本串长为 \(i\)，在 \(Trie\) 上走到编号为 \(j\) 的节点的不可读个数。
如果走到节点 \(j\) 的儿子 \(k\) 这个节点（\(trie[j][k])\) 得到串依然是不可读的，
那么就可以从 $dp[i][j] $ 转移到 $dp[i+1][trie[j][k]] $。
也就是：$dp[i+1][trie[j][k]]+=dp[i][j] $
这个时候不需要想 KMP 那样跳 \(next\) 的原因是我们改变了 \(Trie\) 树使它成为图
随之出现的问题是如何判断走到点 \(j\) 的串是否不可读，回顾一下我们可读的定义：
如果一篇文章中至少包含使用者们了解的一个单词，那么我们说这篇文章是可读的
也就是说，如果节点 \(j\) 的身上有 \(end\) 标记，那么它不可读。
这里有一个易错点： 若一个点的失配指针（\(fail\)) 链 里存在某个单词的 end标记 ,显然这个点是GG的
简单分析时间复杂度：建树 \(O(\Sigma|S|)\) + BFS 求 \(fail\) \(O(\Sigma|S|)\) + DP两重主要循环 \(O(m\Sigma|S|)\) = \((m\Sigma|S|)\) 级别（附常数 26）可过
空间复杂度 \(\Sigma|S|\)
这个算法是可过的！最后， 考虑 DP 的初始状态：\(dp[0][1]=1\) 什么都没有显然是1，注意作者的 \(Trie\) 树标号从1开始。
答案为 \(26^m-\Sigma_{1<=i<=size} dp[m][i]\)
C 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 111;
const int mod = 10007;
int n,m,size=1;
int t[N*N][27],f[N*N];//trie和fail
int dp[N][N*N];
bool ed[N*N];//end标记
char s[N];
void insert(char *s){
int u=1,len=strlen(s);
for(int i=0;i<len;i++){
int ch=s[i]-'A';
if(!t[u][ch])t[u][ch]=++size;
u=t[u][ch];
}
ed[u]=1;
}
void bfs(){
//这个求fail的写法好像和大家的不一样，仔细看看也是对的
for(int i=0;i<26;i++)t[0][i]=1;
queue<int>q;
q.push(1);
while(q.size()){
int u=q.front();q.pop();
for(int i=0;i<26;i++){
if(t[u][i]){
f[t[u][i]]=t[f[u]][i];
q.push(t[u][i]);
if(ed[f[t[u][i]]])ed[t[u][i]]=1;//如果fail可读，自己也可读
}else t[u][i]=t[f[u]][i];
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%s",s);
insert(s);
}
bfs();
dp[0][1]=1;
for(int i=1;i<=m;i++){
for(int j=1;j<=size;j++){
for(int k=0;k<26;k++){
if(!ed[t[j][k]]){
dp[i][t[j][k]]=(dp[i][t[j][k]]+dp[i-1][j])%mod;
}
}
}
}//就不压行
int ans=0;
for(int i=0;i<=size;i++){
ans=(ans+dp[m][i])%mod;
}
int sum=1;
for(int i=1;i<=m;i++){//这里可用快速幂
sum=(sum*26)%mod;
}
printf("%d",(sum-ans+mod)%mod);//小心复数
return 0;
}
D 参考
https://www.luogu.com.cn/blog/_post/62345