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
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
An integer, the number of DNA sequences, mod 100000.
Sample Input
4 3ATACAGAA
Sample Output
36 题意：首先输入的是n和m，分别代表接下来会给你n个病毒串，问你长度为m的不包含病毒的串有多少种 思路：上次写这道题还是半年前及爱情在家写的，当时尚神指导，轻松AC，然而今天奉老大之命前来复习，读题之后发现，蒙蒙哒~~ 首先我们在纸上手动模拟一下或许会对这个题的理解更深刻，我们构建一个AC自动机树，在简单题中，我们已经熟练掌握了建树以及构建fail指针的方式，这道题即是使用到了这个树的一些实际意义。 我们在构建fail指针的时候，加了一部分代码即是
if(en[fail[now]] != 0) { en[now] = 1; } 什么意思呢，我们先来看fail指针的意义，树上每个结点代表一个子串，一个结点的fail指针指向另一个结点，代表的是这个后者是前者的一个后缀，这个在之前应该就是了解的。
然后如果en[fail[now]]!=0 即代表该节点的后缀包含一个病毒串，自然，这个串也是不可以使用的，于是这个点代表的串也是一个病毒串。病毒串是不可以出现的。
接下来我们来讨论为什么AC树是一个状态转移树，每个结点代表的是一个子串，那么从一个串经过next数组到达另一个串，他的意义就是经过一步可以由状态i转换为状态j。有了这句话我们就可以根据现在构建出来的AC树可行的转移路径构建一个转移方程了，部分代码是
void BuildMatrix() { memset(mm.m, 0, sizeof(mm.m)); for(int i=0; i 三个判断条件分别约束的是，状态i，j都存在，状态i代表的子串不是病毒串，状态j代表的子串不是病毒串。
于是我们可以通过一步从状态i转移到状态j，矩阵记录的是转移的方案数，于是++;
接下来回到我们的问题是要长度为m，即由根节点转移m步，于是对一步可到达矩阵求m次幂可得到m步可到达矩阵，再将第0行加起来，即是从根节点m步可以到达的状态
代码如下：
#include#include #include #include #include using namespace std;#define mod 100000int m, n;int cnt['Z'+1];struct MM{ long long m[110][110];};MM mm;MM m1, m2;void init(){ cnt['A'] = 0; cnt['T'] = 1; cnt['C'] = 2; cnt['G'] = 3;}MM mul(MM a, MM b, int siz){ MM c; memset(c.m, 0, sizeof(c.m)); for(int k=0; k