题目传送门(BZOJ)
>原文链接<

题解 :

正难则反, 我们换成求不可行方案数就好做了.

首先建立Trie图

状态 :

F[i][j]表示在Trie图上走了i步, 到了节点j的方案数

转移 :

F[i][j]F[i+1][son[j]]转移, 加法原理, 注意, 当且仅当json[j]都不是危险节点时, 才可以转移

答案 :

26^m减去所有非危险节点的状态的方案数就可以了

代码 :

#include <cstdio>#include <iostream>#include <queue>#include <cstring>using namespace std;const int N = 21000;const int mod = 10007;int ch[N][27], fail[N], n, m, cnt=1;char s[N];bool flg[N];int f[200][N];queue<int>q;void Insert() { int p = 1; int len = strlen(s); for(int i = 0; i < len; i ++ ) { int &k = ch[p][s[i]-'A'+1]; if(!k)k=++cnt; p = k; } flg[p] = 1;}void getFail() { int p; for(int i = 1; i <= 26; i ++ ) ch[0][i] = 1; q.push(1); while(!q.empty()) { p = q.front();q.pop(); for(int i = 1; i <= 26; i ++ ) { if(ch[p][i]) fail[ch[p][i]] = ch[fail[p]][i], q.push(ch[p][i]); else ch[p][i] = ch[fail[p]][i]; } flg[p] |= flg[fail[p]]; }}int main() { scanf("%d%d", &n, &m); for(int i = 1; i <= n; i ++ ) { scanf("%s", s); Insert(); } getFail(); f[0][1] = 1; for(int i = 1; i <= m; i ++ ) for(int p = 1; p <= cnt; p ++ ) { if((!flg[p]) && f[i-1][p]) for(int k = 1; k <= 26; k ++ ) { (f[i][ch[p][k]] += f[i-1][p])%=mod; } } int ans = 1; for(int i = 1; i <= m; i ++ ) (ans *= 26) %= mod; for(int i = 1; i <= cnt; i ++ ) if(!flg[i]) { ((ans-=f[m][i]) += mod) %= mod; } printf("%d\n", ans);}