【POJ 2778】DNA Sequence

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 3
AT
AC
AG
AA

Sample Output

大意：

给出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 #include <cstdio>
 2 #include <cstring>
 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 }