题目大意：有$n$个字符串$s_i$，问有多少个长度为$m$的字符串至少包含$n$个字符串中的一个，字符集 A-Z 。$s_i,m\leqslant100,n\leqslant60$
题解：$AC$自动机上$DP$，转换问题为求有多少个长度为$m$的字符串不包含$n$个字符串中的任意一个。定义$f[i][j]$表示现在字符串长度为$i$，匹配到了$AC$自动机上的点$j$且没有出现$n$个字符串中的任意一个的方案数，发现$f[i][j]$可转移到$f[i+1][nxt[j][k]]$。注意，要求$nxt[j][k]$不能是一个串的结尾。可以发现若$nxt[j][k]$的$fail$中没有串的结尾就是合法的，这一个可以在求$fail$时顺带求出
卡点：无
C++ Code：
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <queue>
const int maxn = 110 * 60, mod = 10007;
inline void reduce(int &x) { x += x >> 31 & mod; } int n, m, ans = 1; namespace AC {
int nxt[maxn][26], fail[maxn], idx = 1;
bool End[maxn];
void insert(std::string s) {
int p = 1;
for (char ch : s) {
if (nxt[p][ch - 'A']) p = nxt[p][ch - 'A'];
else p = nxt[p][ch - 'A'] = ++idx;
}
End[p] = true;
}
void build() {
static std::queue<int> q;
for (int i = 0; i < 26; ++i)
if (nxt[1][i]) fail[nxt[1][i]] = 1, q.push(nxt[1][i]);
else nxt[1][i] = 1;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = 0; i < 26; ++i)
if (nxt[u][i]) {
fail[nxt[u][i]] = nxt[fail[u]][i];
End[nxt[u][i]] |= End[fail[nxt[u][i]]];
q.push(nxt[u][i]);
} else nxt[u][i] = nxt[fail[u]][i];
}
} void solve() {
static std::queue<int> q[2];
int f[111][maxn], tg[maxn];
int now = 1, pst = 0, u;
q[now].push(1);
f[0][1] = 1;
for (int i = 0; i < m; ++i) {
std::swap(now, pst);
while (!q[pst].empty()) {
u = q[pst].front(), q[pst].pop();
for (int j = 0; j < 26; ++j)
if (!End[nxt[u][j]]) {
reduce(f[i + 1][nxt[u][j]] += f[i][u] - mod);
if (tg[nxt[u][j]] != i + 1) q[now].push(nxt[u][j]);
tg[nxt[u][j]] = i + 1;
}
}
}
for (; !q[now].empty(); q[now].pop())
reduce(ans -= f[m][q[now].front()]);
}
} int main() {
std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
std::cin >> n >> m;
for (int i = 1; i <= m; ++i) ans = ans * 26 % mod;
for (int i = 0; i < n; ++i) {
static std::string s;
std::cin >> s;
AC::insert(s);
}
AC::build(), AC::solve();
std::cout << ans << '\n';
return 0;
}