距离上次做AC自动机有很久了=。=，以前这题的思路死活看不懂，现在还是觉得很好理解的。
思路参见：http://blog.csdn.net/morgan_xww/article/details/7834801#。
我用cnt=1表示这个节点是危险的，然后再匹配fail指针的时候，如果一个节点的前缀是危险的，那么这个节点也是危险的，这么维护即可。
顺便一提，我以前的AC自动机模板是没有build过程中失配时的nxt指针的（以前是在match的过程中体现），但是失败时候需要的nxt指针又是很好用的，因此以后的模板中在build中新增这个内容（其实上次的AC自动机DP中就已经有了）。
另外两点可能不是很重要的是：1.我的矩阵模板统一是从1开始的，而这里有0节点；2.在结构体内似乎不能直接初始化字符串= =。
代码如下（我的代码跑的有点慢。。）：
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
const int MAX_Tot = + ;
const int mod = ; int m,n; void add(int &a,int b)
{
a += b;
if(a < ) a += mod;
a %= mod;
} struct matrix
{
int e[MAX_Tot][MAX_Tot],n,m;
matrix() {}
matrix(int _n,int _m): n(_n),m(_m) {memset(e,,sizeof(e));}
matrix operator * (const matrix &temp)const
{
matrix ret = matrix(n,temp.m);
for(int i=;i<=ret.n;i++)
{
for(int j=;j<=ret.m;j++)
{
for(int k=;k<=m;k++)
{
add(ret.e[i][j],1LL*e[i][k]*temp.e[k][j]%mod);
}
}
}
return ret;
}
matrix operator + (const matrix &temp)const
{
matrix ret = matrix(n,m);
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
add(ret.e[i][j],(e[i][j]+temp.e[i][j])%mod);
}
}
return ret;
}
void getE()
{
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
e[i][j] = i==j?:;
}
}
}
}; matrix qpow(matrix temp,int x)
{
int sz = temp.n;
matrix base = matrix(sz,sz);
base.getE();
while(x)
{
if(x & ) base = base * temp;
x >>= ;
temp = temp * temp;
}
return base;
} char way[] = {'A','T','C','G'};
struct Aho
{
struct state
{
int nxt[];
int fail,cnt;
}stateTable[MAX_Tot]; int find(char c) {for(int i=;i<;i++) if(c == way[i]) return i;} int size; queue<int> que; void init()
{
while(que.size()) que.pop();
for(int i=;i<MAX_Tot;i++)
{
memset(stateTable[i].nxt,,sizeof(stateTable[i].nxt));
stateTable[i].fail = stateTable[i].cnt = ;
}
size = ;
} void insert(char *s)
{
int n = strlen(s);
int now = ;
for(int i=;i<n;i++)
{
char c = s[i];
int to = find(c);
if(!stateTable[now].nxt[to])
stateTable[now].nxt[to] = size++;
now = stateTable[now].nxt[to];
}
stateTable[now].cnt = ;
} void build()
{
stateTable[].fail = -;
que.push(); while(que.size())
{
int u = que.front();que.pop();
for(int i=;i<;i++)
{
if(stateTable[u].nxt[i])
{
if(u == ) stateTable[stateTable[u].nxt[i]].fail = ;
else
{
int v = stateTable[u].fail;
while(v != -)
{
if(stateTable[v].nxt[i])
{
stateTable[stateTable[u].nxt[i]].fail = stateTable[v].nxt[i];
// 在匹配fail指针的时候顺便更新cnt
if(stateTable[stateTable[stateTable[u].nxt[i]].fail].cnt == )
stateTable[stateTable[u].nxt[i]].cnt = ;
break;
}
v = stateTable[v].fail;
}
if(v == -) stateTable[stateTable[u].nxt[i]].fail = ;
}
que.push(stateTable[u].nxt[i]);
}
/*****建立自动机nxt指针*****/
else
{
if(u == ) stateTable[u].nxt[i] = ;
else
{
int p = stateTable[u].fail;
while(p != - && stateTable[p].nxt[i] == ) p = stateTable[p].fail;
if(p == -) stateTable[u].nxt[i] = ;
else stateTable[u].nxt[i] = stateTable[p].nxt[i];
}
}
/*****建立自动机nxt指针*****/
}
}
} matrix build_matrix()
{
matrix ans = matrix(size,size);
for(int i=;i<size;i++)
{
for(int j=;j<;j++)
{
if(!stateTable[i].cnt && !stateTable[stateTable[i].nxt[j]].cnt)
ans.e[i+][stateTable[i].nxt[j]+]++;
}
}
return ans;
}
}aho; int main()
{
while(scanf("%d%d",&m,&n) == )
{
aho.init();
char s[];
for(int i=;i<=m;i++)
{
scanf("%s",s);
aho.insert(s);
}
aho.build();
matrix p = aho.build_matrix();
p = qpow(p,n);
int ans = ;
for(int i=;i<=aho.size;i++) add(ans, p.e[][i]);
printf("%d\n",ans);
}
return ;
}