Description
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
大意：
给出M个字符串，求有多少种长度为N且不包含这M个字符串的字符串。（字符串由A、C、G、T组成，M <= 10，N <= 2000000000，每个子串长度长度不超过10）
分析：
要求出不包含子串的字符串的个数，很明显可以用AC自动机 + 动态规划（O(NM^2)）
首先，先读入子串构造一棵 Trie 树，然后在 Trie 树上建立失败指针（BFS），再在 Trie 树上跑一遍动态规划，F[i][j]表示长度为i，最后一个字符对应 Trie 数中第j个节点的方案数，需要注意的是叶子节点不能经过，最后得出的所有节点的方案数之和就是所求的答案。
矩阵乘法快速幂（O(M^2 * logN)）
由于N非常大，所以动态规划肯定会T，但是我们研究数据范围会发现，M和字符串的程度都非常小，实际上按照最坏的情况，Trie 数也只要将数组开到100就够了。
才100？就算100的平方都存的下，100也太小了吧！得好好利用这小小的100。
100个节点，相当于100个状态，100个状态之间的转移，可以枚举一下每个节点指向的4个节点，这样每次转移只要O(4)的时间。但是如果用一个矩阵存下两两之间的连通性（即是否可以转移），这样就需要O(100)的时间来转移，这样明显慢，有什么用呢？
既然说出来当然会有用，原本的转移方程是F[i + 1][Trie[j].To[k]] += F[i][j] （k为0～3），但是如果这样的话转移方程就变成了F[i + 1][k] += F[i][j] * Mat[j][k] （k为0～100，Mat表示能否联通）。
如果换一个角度来看的话，就可以变成F[i][j] = sum (F[i - 1][k] * Mat[k][j]) ，这样的话就变成了一个递推式，而且是一个可以用矩阵乘法快速幂解决的递推式。
那剩下的工作就简单了，构造Mat矩阵，做快速幂，再乘上最后的矩阵就好了。
代码：
1 #include2 #include 3 struct Matrix { 4 int a[110][110]; 5 } mat, ti; 6 int n, m, len, last, tn, ans, f[110], t[110][4], v[110]; 7 char str[11]; 8 void BFS () 9 {10 int q[110], hd, tl;11 for (q[hd = tl = 0] = 0; hd <= tl; hd++)12 for (int i = 0; i < 4; i++)13 t[q[hd]][i] ? (q[hd] ? f[t[q[hd]][i]] = t[f[q[hd]]][i] : 0) ,v[t[q[hd]][i]] |= v[f[t[q[hd]][i]]], q[++tl] = t[q[hd]][i] : t[q[hd]][i] = t[f[q[hd]]][i];14 }15 inline Matrix times (Matrix m1, Matrix m2)16 {17 Matrix ret;18 memset (ret.a, 0, sizeof (ret.a));19 for (int i = 0; i <= tn; i++)20 for (int j = 0; j <= tn; j++)21 for (int k = 0; k <= tn; ret.a[i][j] %= 100000, k++)22 ret.a[i][j] += (long long) m1.a[i][k] * m2.a[k][j] % 100000;23 return ret;24 }25 inline int gc (char ch)26 {27 return ch == 'A' ? 0 : ch == 'C' ? 1 : ch == 'T' ? 2 : 3;28 }29 int main ()30 {31 scanf ("%d %d", &n, &m);32 for (int i = 0; i < n; i++)33 {34 scanf ("%s", (char*) &str);35 len = strlen (str);36 last = 0;37 for (int j = 0, ch = gc (str[j]); j < len; ch = gc (str[++j]))38 last = t[last][ch] ? t[last][ch] : t[last][ch] = ++tn;39 v[last] = 1;40 }41 BFS ();42 for (int i = 0; i <= tn; i++)43 for (int j = 0; j < 4; j++)44 (!v[t[i][j]]) && !v[i] ? mat.a[i][t[i][j]]++ : 0;45 for (int i = 0; i <= tn; i++) ti.a[i][i] = 1;46 for (; m; m >>= 1)47 (m & 1 ? ti = times (ti, mat) : ti), mat = times (mat, mat);48 for (int i = 0; i <= tn; i++) ans += ti.a[0][i];49 printf ("%d", ans % 100000);50 }