先使用AC自动机求得状态转移关系，再建立矩阵，mat[i][j]表示一步可从i到j且i,j节点均非终止字符的方案数，则此矩阵的n次方表示n步从i,到j的方法数。
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std; typedef long long LL;
const int N = 500, CH = 4;
struct Trie{
Trie *next[CH];
Trie *fail;
int cnt, id;
}tree[N]; int Hash[128];
bool flag[1008];
int chi[108][4]; const LL MOD = 100000;
int num;
struct Mat{
LL mat[108][108]; Mat(){
for(int i = 0; i <= num; i++){
for(int j = 0; j <= num; j++){
mat[i][j] = 0;
}
}
}
Mat operator*(const Mat &b){
Mat res;
for(int i = 0;i <= num; i++){
for(int j = 0; j <= num; j++){
for(int k = 0; k <= num; k++){
if(mat[i][k] == 0 || b.mat[k][j] == 0){
continue;
}
res.mat[i][j] += (mat[i][k] * b.mat[k][j])%MOD;
}
res.mat[i][j] %= MOD;
}
}
return res;
}
Mat operator^(LL k){
Mat res;
Mat a = *this;
for(int i = 0; i <= num; i++){
res.mat[i][i] = 1;
}
while(k){
if(k%2){
res = res * a;
}
a = a * a;
k /= 2;;
}
return res;
}
}; class ACauto{
public:
int nxt;
Trie *root; ACauto(){
root = &tree[0];
nxt=0;
memset(&tree[0], 0, sizeof(Trie));
} void insert(char *s){
Trie *p = root;
for(int i = 0; s[i]; i++){
int c = Hash[s[i]];
if(!p -> next[c]){
memset(&tree[++nxt], 0, sizeof(Trie));
p -> next[c] = &tree[nxt];
p -> next[c] -> id = nxt;
}
p = p -> next[c];
}
p -> cnt++;
flag[p -> id] = 1;
} void build(){
queue<Trie *> q;
q.push(root);
root -> fail = NULL;
while(!q.empty()){
Trie *cur = q.front();
q.pop();
//是否为终止结点
if(cur ->fail && cur != root && flag[cur->fail->id]){
flag[cur->id] = 1;
} for(int i = 0; i < CH; i++){
Trie *son = cur -> next[i];
Trie *tp = (cur == root)? root: cur -> fail->next[i];
if(son == NULL){
cur -> next[i] = tp;
}else{
son -> fail = tp;
q.push(son);
}
son = cur -> next[i];
//儿子节点
chi[cur -> id][i] = son -> id;
}
}
} }; char str[1008];
int main(){
Hash['A'] = 0;
Hash['C'] = 1;
Hash['G'] = 2;
Hash['T'] = 3;
int m;
LL n;
while(~scanf("%d %I64d", &m, &n)){
ACauto ac;
memset(flag, 0, sizeof(flag));
memset(chi, -1, sizeof(chi));
for(int i = 0; i < m; i++){
scanf("%s", str);
ac.insert(str);
}
ac.build();
num = ac.nxt;
Mat mt;
//mat[i][j]表示一步可从i到j且i,j节点均非终止字符的方案数
for(int i = 0; i <= num ; i++){
for(int j = 0; j < 4; j++){
if(flag[chi[i][j]] == 0){
mt.mat[i][chi[i][j]]++;
}
}
}
mt = mt ^ n;
LL res = 0;
for(int i = 0; i <= num; i++){
res = (res + mt.mat[0][i]) % MOD;
}
printf("%I64d\n", res); }
return 0;
}