有$m$个DNA串，你需要构造一个长度为$n$的DNA序列，使得其中不出现任何一个DNA串，求方案数。
虽说是自动机的入门题，但作为一个矩阵不会自动机会的蒟蒻来说，还是写一下吧。。
首先我们考虑这样一个问题:
有一副$n$个点的有向图，问从源点$s$开始恰好经过$k$条边，求可能的路径个数。
这个问题很经典，把边用邻接矩阵存，然后就相当于在做一个简单的dp，在$k$很大的情况下，矩阵优化一下即可。
然后看这道题，能否出现一个串可以构成一幅图吧，我们用AC自动机上的节点对应图上的节点。对于当前点，接下来可以加4个点，如果添加一个点后沿着自动机的边走到了一个串的结尾，那么在邻接表上这条边对应的自动机上的节点的边边权为0，否则边权为1
然后瞎比矩阵快速幂一下即可。
#include<iostream>
#include<algorithm>
#include<string.h>
#include<stdio.h>
using namespace std;
const int M=1e4+5;
const int N=105;
const int P=100000;
#define bug(x) cout<<#x<<"="<<x<<" "
#define debug(x) cout<<#x<<"="<<x<<endl
inline void Mod_add(int &a,int b){
if((a+=b)>=P)a-=P;
}
inline void Mod_sub(int &a,int b){
if((a-=b)<0)a+=P;
}
inline int Mod(int x){
if(x>=P)return x-P;
if(x<0)return x+P;
return x;
}
struct node{
int to[5],d,g;
}tr[M];
int allc=1;
struct Mat{
int A[N][N];
Mat(){
for(int i=1;i<=allc;++i)
for(int j=1;j<=allc;++j)
A[i][j]=0;
}
inline Mat operator * (const Mat &tmp)const{
Mat res;
for(int k=1;k<=allc;++k){
for(int i=1;i<=allc;++i){
if(!A[i][k])continue;
for(int j=1;j<=allc;++j)
Mod_add(res.A[i][j],1ll*A[i][k]*tmp.A[k][j]%P);
}
}
return res;
}
inline void units(){
for(int i=1;i<=allc;++i)
A[i][i]=1;
}
};
inline Mat Mod_Pow(Mat &x,int a){
Mat res;res.units();
for(;a;a>>=1,x=x*x)
if(a&1)res=res*x;
return res;
}
char str[100];
inline int id(char c){
switch(c){
case('A'):return 0;
case('T'):return 1;
case('C'):return 2;
case('G'):return 3;
}
}
inline void Insert(){
int len=strlen(str),rt=1;
for(int i=0;i<len;++i){
int c=id(str[i]);
if(!tr[rt].to[c])tr[rt].to[c]=++allc;
rt=tr[rt].to[c];
}
tr[rt].d=1;
}
int que[(int)1e4+5];
inline void build(){
int l=0,r=0;
for(que[r++]=1;l<r;){
int u=que[l++];
for(int i=0,j,s;i<4;++i){
for(j=tr[u].g;j;j=tr[j].g)
if(tr[j].to[i])break;
if(s=tr[u].to[i]){
tr[s].g=j?tr[j].to[i]:1;
tr[s].d|=tr[tr[s].g].d;
que[r++]=s;
}
else tr[u].to[i]=j?tr[j].to[i]:1;
}
}
}
int main(){
int m,n;cin>>m>>n;
for(int i=1;i<=m;++i){
scanf("%s",str);
Insert();
}
build();
Mat ord;
for(int i=1;i<=allc;++i)
for(int j=0;j<4;++j)
ord.A[i][tr[i].to[j]]+=tr[tr[i].to[j]].d^1;
Mat ans=Mod_Pow(ord,n);
int res=0;
for(int i=1;i<=allc;++i)
Mod_add(res,ans.A[1][i]);
cout<<res<<endl;
return 0;
}