It's well known that DNA Sequence is a sequence only contains A, C, T and G, and it's very useful to analyze a segment of DNA Sequence，For example, if a animal's DNA sequence contains segment ATC then it may mean that the animal may have a genetic disease. Until now scientists have found several those segments, the problem is how many kinds of DNA sequences of a species don't contain those segments.
Suppose that DNA sequences of a species is a sequence that consist of A, C, T and G，and the length of sequences is a given integer n.
Input
Suppose that DNA sequences of a species is a sequence that consist of A, C, T and G，and the length of sequences is a given integer n.
First line contains two integer m (0 <= m <= 10), n (1 <= n <=2000000000). Here, m is the number of genetic disease segment, and n is the length of sequences.
Next m lines each line contain a DNA genetic disease segment, and length of these segments is not larger than 10.
Output
Next m lines each line contain a DNA genetic disease segment, and length of these segments is not larger than 10.
An integer, the number of DNA sequences, mod 100000.
Sample Input
4 3 AT AC AG AASample Output
36
题目思路：
其与E、F题类似，都是求给定长度不含某些序列的数量。
不过这里有一个特点就是其字符串长度很长，肯定无法用DP来做，
类比一下，其答案就是在一个图上有多少条长度为N的路径，这里就想到了通过矩阵快速幂的log(n)的时间复杂度来做。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(int i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
const int inf_int = 2e9;
const long long inf_ll = 2e18;
#define inf_add 0x3f3f3f3f
#define MOD 100000
#define pb push_back
//#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=5e2+10;
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef unsigned long long ull;
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
//#pragma comment(linker, "/STACK:102400000,102400000")
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
int dir[8][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
map<char, int> mp;
struct Matrix
{
unsigned long long mat[110][110];
int n;
Matrix(){}
Matrix(int _n)
{
n=_n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
mat[i][j] = 0;
}
Matrix operator *(const Matrix &b)const
{
Matrix ret = Matrix(n);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
for(int k=0;k<n;k++)
{
ret.mat[i][j]=(ret.mat[i][j]+mat[i][k]*b.mat[k][j]) % MOD;
}
return ret;
}
};
unsigned long long pow_m(unsigned long long a,int n)
{
unsigned long long ret=1;
unsigned long long tmp = a;
while(n)
{
if(n&1)ret*=tmp;
tmp*=tmp;
n>>=1;
}
return ret;
}
Matrix pow_M(Matrix a,int n)
{
Matrix ret = Matrix(a.n);
for(int i=0;i<a.n;i++)
ret.mat[i][i] = 1;
Matrix tmp = a;
while(n)
{
if(n&1)ret=ret*tmp;
tmp=tmp*tmp;
n>>=1;
}
return ret;
}
const int N = 1005;
const int M = 51;
class Trie
{
public:
int next[N][M],fail[N],end[N];
int root,L;
int newnode()
{
for(int i = 0;i < M;i++)//每一个节点对应0-128中的任意一个。
next[L][i] = -1;
end[L++] = -1;//表示下面没有节点 初始化，如果是记录次数，就赋0 还可以赋任意的数，
return L-1;
}
void init()
{
L = 0;
root = newnode();
}
void insert(char s[])
{
int len = strlen(s);
int now = root;
for(int i = 0;i < len;i++)
{
if(next[now][mp[s[i]]] == -1)
next[now][mp[s[i]]] = newnode();
now=next[now][mp[s[i]]];//记录其对应的节点编号
}
end[now]=1;//记录当前匹配单词的节点
//end[now]++;也可以用匹配单词结束后来记录次数
}
void build()
{
queue<int>Q;
fail[root] = root;//根节点仍然是根节点
for(int i = 0;i < M;i++)//对第一个字符遍历
if(next[root][i] == -1)//没有此字符开头
next[root][i] = root;//跳转到根
else//有此字符开头的
{
fail[next[root][i]] = root;//这个行位的失败指针为根
Q.push(next[root][i]);//行放入队列
}
while(!Q.empty())//还有字符
{
int now = Q.front();//逐层拿出第一个
Q.pop();
if(end[fail[now]]== 1) end[now] = 1;
for(int i = 0;i < M;i++)//对这一行
if(next[now][i] == -1)//如果下一行没有这个字符
next[now][i] = next[fail[now]][i];//他的下一个的这
else//如果有这个字符
{
fail[next[now][i]] = next[fail[now]][i];//他的下一个的
Q.push(next[now][i]);//下一行继续
}
}
}
/*bool used[N];//判断其是否被查找到
bool query(char buf[],int n,int id)
{
int len = strlen(buf);
int now = root;
memset(used,false,sizeof(used));//初始化used
bool flag = false;
for(int i = 0;i < len;i++)
{
now = next[now][buf[i]];
int temp = now;
while(temp != root)
{
if(end[temp] != -1)
{
used[end[temp]] = true;//记录被匹配的信息
flag = true;
}
temp = fail[temp];
}
}
}*/
Matrix getMatrix()
{
Matrix ret = Matrix(L+1);
for(int i = 0;i < L;i++)
{
if(end[i]==1) continue;
for(int j = 0;j < 4;j++)
{
if(end[next[i][j]]==1) continue;
ret.mat[i][next[i][j]] ++;
}
}
return ret;
}
};
char buf[10005];
int m,p;
Trie ac;
int main()
{
mp.clear();
mp['A'] = 0;
mp['C'] = 1;
mp['T'] = 2;
mp['G'] = 3;
while(~scanf("%d %d",&p,&m))
{
ac.init();
while(p--)
{
scanf("%s", buf);
ac.insert(buf);
}
ac.build();
Matrix E = ac.getMatrix();
Matrix ans = pow_M(E,m);
int number = 0;
for(int i = 0;i < ac.L;i++){
number += ans.mat[0][i];
number %= MOD;
}
printf("%d\n",number);
}
return 0;
}