Blackops

初心易得，始终难守

0%

POJ 2778 DNA Sequence(AC自动机+矩阵快速幂)

发表于 更新于 分类于 ， ，

DNA Sequence
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 17760 Accepted: 6834

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

36

题目链接：POJ 2778

其实题目可以转化为从Trie树根节点走n步所形成的不同的合法路径种类，其中合法路径是指输入的这几个字符串均不能出现。
把AC自动机上的路径和fail指针看成一幅图，可以沿着这两种边走n次，最后求出到达各个点的方案数之和即可，这显然是用邻接矩阵+快速幂就可以了，要注意的是上一个fail指向的是单词的末尾节点，那么当前的节点也将成为末尾节点，因为fail走的是当前路径后缀与指向路径的最长前缀末尾，因此如果走fail这个点，那么前面的前缀必然会在当前路径的后缀中出现，因此要考虑进去
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include <stdio.h>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <bitset>
#include <string>
#include <stack>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 12;
const LL mod = 100000LL;
struct Trie
{
    int nxt[4];
    int fail, cnt;
    void init()
    {
        fill(nxt, nxt + 4, -1);
        fail = cnt = 0;
    }
} L[N * N];
int sz;
int id[150];
char s[N];

struct Mat
{
    LL A[105][105];
    void zero()
    {
        for (int i = 0; i < sz; ++i)
            for (int j = 0; j < sz; ++j)
                A[i][j] = 0;
    }
    void one()
    {
        zero();
        for (int i = 0; i < sz; ++i)
            A[i][i] = 1;
    }
    Mat operator*(Mat b)
    {
        Mat c;
        c.zero();
        for (int i = 0; i < sz; ++i)
        {
            for (int k = 0; k < sz; ++k)
            {
                if (!A[i][k])
                    continue;
                for (int j = 0; j < sz; ++j)
                {
                    if (!b.A[k][j])
                        continue;
                    c.A[i][j] = (c.A[i][j] + A[i][k] * b.A[k][j]) % mod;
                }
            }
        }
        return c;
    }
    friend Mat operator^(Mat a, LL b)
    {
        Mat ret;
        ret.one();
        while (b)
        {
            if (b & 1)
                ret = ret * a;
            a = a * a;
            b >>= 1;
        }
        return ret;
    }
} A;

namespace Aho
{
    void init()
    {
        sz = 0;
        L[sz++].init();
    }
    void ins(char *s)
    {
        int len = strlen(s);
        int u = 0;
        for (int i = 0; i < len; ++i)
        {
            int v = id[s[i]];
            if (L[u].nxt[v] == -1)
            {
                L[sz].init();
                L[u].nxt[v] = sz++;
            }
            u = L[u].nxt[v];
        }
        L[u].cnt = 1;
    }
    void build()
    {
        queue<int>Q;
        L[0].fail = 0;
        for (int i = 0; i < 4; ++i)
        {
            if (L[0].nxt[i] == -1)
                L[0].nxt[i] = 0;
            else
            {
                L[L[0].nxt[i]].fail = 0;
                Q.push(L[0].nxt[i]);
            }
        }
        while (!Q.empty())
        {
            int u = Q.front();
            Q.pop();
            int uf = L[u].fail;
            if (L[uf].cnt)
                L[u].cnt = 1;
            for (int i = 0; i < 4; ++i)
            {
                int v = L[u].nxt[i];
                if (v == -1)
                    L[u].nxt[i] = L[uf].nxt[i];
                else
                {
                    L[v].fail = L[uf].nxt[i];
                    Q.push(v);
                }
            }
        }
    }
}
int main(void)
{
    id['A'] = 0;
    id['G'] = 1;
    id['T'] = 2;
    id['C'] = 3;
    int m, n, i, j;
    while (~scanf("%d%d", &m, &n))
    {
        Aho::init();
        while (m--)
        {
            scanf("%s", s);
            Aho::ins(s);
        }
        Aho::build();
        A.zero();
        for (i = 0; i < sz; ++i)
        {
            for (j = 0; j < 4; ++j)
            {
                int v = L[i].nxt[j];
                if (L[v].cnt)
                    continue;
                ++A.A[i][v];
            }
        }
        A = A ^ n;
        LL ans = 0;
        for (int i = 0; i < sz; ++i)
            ans = (ans + A.A[0][i]) % mod;
        printf("%lld\n", ans);
    }
    return 0;
}