一直不理解到底怎么做啊,想了好久$TwT$

最后终于明白了为什么找到第一个满足条件的$fail$就计算,因为避免重复,这个回答,,,

然后$root$下面要接上26个节点,这里26个字母中不在字典内的都用$f[i][0]$代替了,这个也想了好久,$==$我还是回家种地吧。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define mo 10007
#define N 103
#define M 6003
using namespace std;
int q[M], c[M][26], w[M], fail[M], f[N][M], n, m, cnt = 0;
inline void ins(char *s) {
int len = strlen(s), now = 0;
for(int i = 0; i < len; ++i) {
int t = s[i] - 'A';
if (!c[now][t])
c[now][t] = ++cnt;
now = c[now][t];
}
w[now] = 1;
}
inline void BFS() {
int head = 0, tail = 1, now = 0;
q[1] = 0;
while (head != tail) {
now = q[++head];
for(int t = 0; t < 26; ++t)
if (c[now][t]) {
q[++tail] = c[now][t];
if (now == 0) continue;
int tmp = fail[now];
while (tmp && !c[tmp][t])
tmp = fail[tmp];
fail[c[now][t]] = c[tmp][t];
if (w[c[tmp][t]])
w[c[now][t]] = 1; //!!!!!!!
}
}
}
inline int ipow(int x, int nn) {
int ans = 1;
for(int t = x; nn; nn >>= 1, t = (t * t) % mo)
if (nn & 1) {
ans = (ans * t);
if (ans >= mo)
ans = ans % mo;
}
return ans;
}
inline void AC() {
f[0][0] = 1;
for(int i = 0; i <= m; ++i)
for(int j = 0; j <= cnt; ++j)
if (f[i][j]) {
for(int t = 0; t < 26; ++t) {
int tmp = j;
while (tmp && !c[tmp][t])
tmp = fail[tmp];
tmp = c[tmp][t];
if (!w[tmp]) {
f[i + 1][tmp] += f[i][j];
if (f[i + 1][tmp] >= mo)
f[i + 1][tmp] %= mo;
}
}
}
int _ = 0, al = ipow(26, m);
for(int i = 0; i <= cnt; ++i)
if (!w[i]) {
_ += f[m][i];
if (_ > mo)
_ %= mo;
}
int ans = ((al - _) % mo + mo) %mo;
printf("%d\n", ans);
}
int main() {
scanf("%d%d", &n, &m);
char s[N];
for(int i = 1; i <= n; ++i)
scanf("%s", s), ins(s);
BFS();
AC();
return 0;
}

最后终于做出来了,因为看了别人的模板,,,,这,,,

04-29 00:11