看此题前先看一下matrix67大神写的关于十个矩阵的题目中的一个，如下：
经典题目8 给定一个有向图，问从A点恰好走k步（允许重复经过边）到达B点的方案数mod p的值
把给定的图转为邻接矩阵，即A(i,j)=1当且仅当存在一条边i->j。令C=A*A，那么C(i,j)=ΣA(i,k)*A(k,j)，实际上就等于从点i到点j恰好经过2条边的路径数（枚举k为中转点）。类似地，C*A的第i行第j列就表示从i到j经过3条边的路径数。同理，如果要求经过k步的路径数，我们只需要二分求出A^k即可。
再来看此题，与1627是如此的相似，又如此的不同，怒把长度涨到20Y，普通的dp转移无法奏效。
既然已经贴上了大神的讲解，肯定与之有关系，姑且直接拉近距离，我们建立的trie树是有路径可寻的，从root往下走，显然，它是一个有向图，root->a可达 说明他俩之间右边，
抛开病毒不病毒的不讲，长度为n的字符串数不就是从root走n步到达某个j结点的方案数？，那么此题就基本解决了，最后一点是构造A这个矩阵，需要当前结点不为病毒结点。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 101
#define LL long long
#define INF 0xfffffff
#define mod 100000
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
const int child_num = ;
const int _n = ;
char vir[];
struct Mat
{
LL mat[N][N];
};
Mat operator * (Mat a,Mat b)
{
Mat c;
memset(c.mat,,sizeof(c.mat));
int i,j,k;
for(k = ; k < _n ; k++)
{
for(i = ; i < _n ;i++)
{
if(a.mat[i][k]==) continue;//优化
for(j = ;j < _n;j++)
{
if(b.mat[k][j]==) continue;//优化
c.mat[i][j] = (c.mat[i][j]+(a.mat[i][k]*b.mat[k][j])%mod)%mod;
}
}
}
return c;
}
Mat operator ^(Mat a,int k)
{
Mat c;
int i,j;
for(i = ; i < _n ;i++)
for(j = ; j < _n ;j++)
c.mat[i][j] = (i==j);
for(; k ;k >>= )
{
if(k&) c = c*a;
a = a*a;
}
return c;
}
class AC
{
private:
int ch[N][child_num];
int Q[N];
int fail[N];
int val[N];
int id[];
int sz;
public:
void init()
{
fail[] = ;
id['A'] = ; id['G'] = ;
id['T'] = ; id['C'] = ;
}
void reset()
{
memset(val,,sizeof(val));
memset(fail,,sizeof(fail));
memset(ch[],,sizeof(ch[]));
sz = ;
}
void insert(char *s,int key)
{
int i,k = strlen(s);
int p = ;
for(i = ;i < k ;i++)
{
int d = id[s[i]];
if(ch[p][d]==)
{
memset(ch[sz],,sizeof(ch[sz]));
ch[p][d] = sz++;
}
p = ch[p][d];
}
val[p] = key;
}
void construct()
{
int i,head=,tail = ;
for(i = ; i < child_num ; i++)
{
if(ch[][i])
{
Q[tail++] = ch[][i];
fail[ch[][i]] = ;
}
}
while(head!=tail)
{
int u = Q[head++];
val[u]|=val[fail[u]];
for(i = ;i < child_num ; i++)
{
if(ch[u][i])
{
Q[tail++] = ch[u][i];
fail[ch[u][i]] = ch[fail[u]][i];
}
else ch[u][i] = ch[fail[u]][i];
}
}
}
void work(int n)
{
Mat x;
int i,j;
memset(x.mat,,sizeof(x.mat));
for(i = ; i < sz ; i++)
for(j = ; j < child_num ; j++)
if(!val[ch[i][j]])
x.mat[i][ch[i][j]]++;
x = x^n;
int ans = ;
for(i = ;i < sz ; i++)
ans = (ans+x.mat[][i])%mod;
printf("%d\n",ans);
}
}ac;
int main()
{
int m,n;
ac.init();
while(cin>>m>>n)
{
ac.reset();
while(m--)
{
scanf("%s",vir);
ac.insert(vir,);
}
ac.construct();
ac.work(n);
}
return ;
}