题意:给定n个不能出现的模式串，给定一个长度m，要求长度为m的合法串有多少种。
思路：用AC自动机，利用AC自动机上的节点做矩阵乘法。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#include<queue>
#define MOD 100000
char s[];
int ch(char x){
if (x=='A') return ;
if (x=='C') return ;
if (x=='G') return ;
if (x=='T') return ;
return -;
}
struct Trie{
int fail[],next[][],end[],L,root;
int newnode(){
for (int i=;i<;i++)
next[L][i]=-;
end[L++]=-;
return L-;
}
void clear(){
L=;
root=newnode();
}
void insert(char s[]){
int len=strlen(s),now=root;
for (int i=;i<len;i++){
if (next[now][ch(s[i])]==-) next[now][ch(s[i])]=newnode();
now=next[now][ch(s[i])];
}
end[now]=;
}
void build(){
std::queue<int>Q;
int now;
for (int i=;i<;i++)
if (next[root][i]==-)
next[root][i]=root;
else{
fail[next[root][i]]=root;
Q.push(next[root][i]);
}
while (!Q.empty()){
now=Q.front();Q.pop();
if (end[fail[now]]==) end[now]=;
for (int i=;i<;i++){
if (next[now][i]==-) next[now][i]=next[fail[now]][i];
else{
fail[next[now][i]]=next[fail[now]][i];
Q.push(next[now][i]);
}
}
}
}
}ac;
struct Matrix{
int n,mx[][];
Matrix(){}
Matrix(int x){
n=x;
for (int i=;i<n;i++)
for (int j=;j<n;j++)
mx[i][j]=;
}
};
Matrix operator *(Matrix a,Matrix b){
int n=a.n;
Matrix c=Matrix(n);
for (int i=;i<n;i++)
for (int j=;j<n;j++)
for (int k=;k<n;k++){
int tmp=(long long) a.mx[i][k]*b.mx[k][j]%MOD;
c.mx[i][j]=(c.mx[i][j]+tmp)%MOD;
}
return c;
}
Matrix powm(Matrix t,int m){
Matrix r=Matrix(t.n);
for (int i=;i<=t.n;i++)
r.mx[i][i]=;
while (m){
if (m%) r=r*t;
t=t*t;
m/=;
}
return r;
}
int main(){
int m;
int n;
while (scanf("%d%d",&n,&m)!=EOF){
ac.clear();
for (int i=;i<n;i++){
scanf("%s",s);
ac.insert(s);
}
ac.build();
Matrix a=Matrix(ac.L);
for (int i=;i<ac.L;i++)
for (int j=;j<;j++)
if (ac.end[ac.next[i][j]]==-)
a.mx[i][ac.next[i][j]]++;
a=powm(a,m);
int ans=;
for (int i=;i<a.n;i++)
ans=(ans+a.mx[][i])%MOD;
printf("%d\n",ans);
}
}