#include <iostream>
#include <string.h>
using namespace std;
#define MAXN 100
#define FAIL 0
int trans[MAXN][26];
bool terminal[MAXN];
int S[MAXN];
int vex;
const int mod = 10007;
void init() 
{
fill(trans[1], trans[vex + 1], FAIL);
fill(terminal, terminal + vex + 1, false);
vex = 1;
}
void trie(char *p) {
int cur = 1, ch;
while (*p != '\0') {
ch = *(p++) - 'A';
if (trans[cur][ch] == FAIL) trans[cur][ch] = ++vex;
cur = trans[cur][ch];
}
terminal[cur] = true;
}
void build_ac() {
int Q[MAXN], f, r;
f = r = 0;
S[1] = FAIL;
Q[r++] = 1;
while (f < r) {
int cur = Q[f++];
for (int i = 0; i < 26; i++) {
int next = trans[cur][i];
if (next != FAIL) {
if (cur == 1) S[next] = cur;
else S[next] = trans[S[cur]][i];
if (terminal[S[next]]) terminal[next] = true;
Q[r++] = next;
} else {
if (cur == 1) trans[cur][i] = 1;
else trans[cur][i] = trans[S[cur]][i];
}
}
}
}
typedef int MATR[MAXN][MAXN];
MATR omat;
int n;
int conv[MAXN];
int getid(int cur) {
if (conv[cur] == -1) conv[cur] = n++;
return conv[cur];
}
void calmat() {
int i, j, ch, cur, next;
memset(omat, 0, sizeof(omat));
fill(conv, conv + vex + 1, -1);
n = 0;
for (cur = 1; cur <= vex; cur++) {
if (terminal[cur]) continue;
i = getid(cur);
for (ch = 0; ch < 26; ch++) {
next = trans[cur][ch];
if (terminal[next]) continue;
j = getid(next);
if (next != FAIL) omat[i][j]++;
}
}
}
void matmul(MATR a, MATR b, MATR c, int n) {
int i, j, k;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
c[i][j] = 0;
for (k = 0; k < n; k++)
c[i][j] += a[i][k] * b[k][j];
c[i][j] %= mod;
}
}
}
void matpow(MATR a, MATR c, int m) { //a^m
if (m == 1) {
memcpy(c, omat,sizeof(MATR));
return;
}
matpow(c, a, m/2);
matmul(a, a, c, n);
if (m & 1) {
matmul(c, omat, a, n);
memcpy(c, a, sizeof(MATR));
}
}
int modpow(int a, int m) {
if (m == 1) return a % mod;
int tmp = modpow(a, m/2);
tmp = tmp * tmp % mod;
if (m & 1) tmp = tmp * a % mod;
return tmp;
}
int main() {
#ifdef _DEBUG
freopen("in.txt", "r", stdin);
#endif
int m, len, i;
char buf[100];
while (scanf("%d%d", &m, &len) != EOF) {
init();
for (i = 0; i < m; i++) {
scanf("%s", buf);
trie(buf);
}
build_ac();
calmat();
MATR tmp, res;
matpow(tmp, res, len);
int bad = 0;
for (i = 0; i < n; i++) bad -= res[0][i];
bad = (bad % mod + mod) % mod;
int total = modpow(26, len);
printf("%d\n", (total + bad) % mod);
}
return 0;
}
版本2
#include <stdio.h>
#include <string.h>
#define R 27
#define N 100
#define M 10007
typedef int LL;
int tree[N][R], flag[N], fail[N], state;
void init(){
memset(tree, -1, sizeof(tree));
memset(flag, 0, sizeof(flag));
memset(fail, -1, sizeof(fail));
flag[0] = 0;
state = 1;
}
void insert(char ch[]) {
int p = 0, i = 0, t;
while(ch[i]) {
t = ch[i] - 'A' + 1;
if(tree[p][t] < 0) tree[p][t] = state++;
p = tree[p][t], i ++;
}
flag[p] = 1;
}
int que[N];
void get_fail() {
int close = -1, open = 0, next;
que[0] = 0;
fail[0] = -1;
while(close < open) {
int p = que[++close];
for(int i = 0; i < R; i ++) {
next = tree[p][i];
if(next == -1){
if(p == 0) tree[p][i] = 0;
else tree[p][i] = tree[fail[p]][i];
} else {
if(p == 0) fail[next] = 0;
else fail[next] = tree[fail[p]][i];
if(flag[fail[next]]) flag[next] = true;
que[++open] = next;
}
}
}
}
int n, L;
LL f[N][N], sum = 0;
void mod_multi(LL a[N][N], LL b[N][N], int r){
int i, j, k;
LL c[N][N] = {};
for (k = 0; k < r; k++)
for (i = 0; i < r; i++)
if(a[i][k])
for (j = 0; j < r; j++){
c[i][j] += a[i][k] * b[k][j];
c[i][j] %= M;
}
for (i = 0; i < r; i++)
for (j = 0; j < r; j++)
a[i][j] = c[i][j];
}
void mod_exp(LL a[N][N], LL n, int r){
int i, j, k;
LL ans[N][N] = {};
for (i = 0; i < r; i++)ans[i][i] = 1;
for (; n; n >>= 1){
if (n & 1)
mod_multi(ans, a, r);
mod_multi(a, a, r);
}
for (i = 0; i < r; i++)
for (j = 0; j < r; j++)
a[i][j] = ans[i][j];
}
LL fast(LL sum, int L) {
LL temp = 1ll;
for(;L;L >>= 1) {
if(L&1) {
temp *= sum;
temp %= M;
}
sum *= sum;
sum %= M;
}
return temp;
}
int main() {
while(scanf("%d %d\n", &n ,&L) != EOF) {
char str[7];
init();
for(int i = 0; i < n; i ++) {
gets(str);
insert(str);
}
get_fail();
int map[N], cnt = 0, next;
memset(map,-1,sizeof(map));
memset(f, 0, sizeof(f));
for(int i = 0; i < state; i ++) {
if(flag[i]) continue;
for(int j = 1; j < R; j ++) {
next = tree[i][j];
if(flag[next])
continue;
if(map[i] == -1) map[i] = cnt ++;
if(map[next] == -1) map[next] = cnt ++;
f[map[i]][map[next]] ++;
}
}
mod_exp(f, L, cnt);
LL ans = 0;
for(int i = 0; i < cnt; i ++) ans += f[0][i];
ans %= M;
sum = fast(26, L);
printf("%d\n", (sum + M - ans) % M);
}
}