AC自动机上dp第一题嗷。
如果直接求可读文本的数量，显然要容斥，不好搞。 于是考虑求不可读文本的数量，再用\(26^m\)减去其即可。 建出AC自动机，如果一个节点为单词结尾或其fail链中有节点为单词结尾，那么这个点就不能走，这个显然可以在bfs的时候顺便求出来。 然后就是大家熟知的方案数dp了，\(f[n][m]\)表示走到节点\(n\)用\(m\)步的方案数，转移就不说了。 最后答案就是\(26^m-\sum_{i=1}^mf[i][m]\)#include#include #include #include using namespace std;const int MAXN = 60010;const int MAXM = 110;const int MOD = 10007;struct Node{ int fail, next[26];}AC[MAXN];int n, u, cnt, m;queue q;int ban[MAXN], f[MAXN][MAXM];char a[MAXN];void insert(){ int len = strlen(a + 1), w; u = 0; for(int i = 1; i <= len; ++i){ w = a[i] - 'A'; if(!AC[u].next[w]) AC[u].next[w] = ++cnt; u = AC[u].next[w]; } ban[u] = 1;}void BuildFail(){ u = 0; for(int i = 0; i < 26; ++i) if(AC[u].next[i]) q.push(AC[u].next[i]); while(q.size()){ u = q.front(); q.pop(); ban[u] |= ban[AC[u].fail]; for(int i = 0; i < 26; ++i) if(AC[u].next[i]){ q.push(AC[u].next[i]); AC[AC[u].next[i]].fail = AC[AC[u].fail].next[i]; } else AC[u].next[i] = AC[AC[u].fail].next[i]; }}int fast_pow(int n, int k){ int ans = 1; while(k){ if(k & 1) ans = ans * n % MOD; n = n * n % MOD; k >>= 1; } return ans;}int ans;int main(){ scanf("%d%d", &n, &m); for(int i = 1; i <= n; ++i){ scanf("%s", a + 1); insert(); } BuildFail(); f[0][0] = 1; for(int i = 1; i <= m; ++i) for(int j = 0; j <= cnt; ++j) for(int k = 0; k < 26; ++k) if(!ban[AC[j].next[k]]) f[AC[j].next[k]][i] = (f[AC[j].next[k]][i] + f[j][i - 1]) % MOD; ans = fast_pow(26, m); for(int i = 0; i <= cnt; ++i) ans = (ans - f[i][m] + MOD) % MOD; printf("%d\n", ans); return 0;}