DNA Sequence
| Time Limit: 1000MS |
|
Memory Limit: 65536K |
| Total Submissions: 8107 |
|
Accepted: 2943 |
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
Source
POJ Monthly--2006.03.26,dodo
不會做啊不會做啊
ac自動機切不動啊
http://hi.baidu.com/lilymona/item/fd18390b1885df883d42e25f題解姑且就看這里吧
trie圖構出狀態之間的關系矩陣為A
則A^n的第一行的和即為所求
why？
1
#include <cstdio>
2#include <cstdlib>
3#include <cstring>
4#include <cmath>
5#include <ctime>
6#include <cassert>
7#include <iostream>
8#include <sstream>
9#include <fstream>
10#include <map>
11#include <set>
12#include <vector>
13#include <queue>
14#include <algorithm>
15#include <iomanip>
16using namespace std;
17#define maxn 105
18#define MOD 100000
19int n,m;
20int root,head,tail,sind;
21int q[maxn*maxn];
22char str[15];
23int hash[300];
24struct node
25
{
26
int next[4];
27 int count,fail;
28 void init()
29
{
30 memset(next,-1,sizeof(next));
31 fail=-1;
32 count=0;
33
}
34
} s[maxn];
35struct matrix
36{
37 int y,x;
38 long long m[maxn][maxn];
39 void init()
40 {
41 memset(m,0,sizeof(m));
42 y=0;
43 x=0;
44 }
45 void init(int a,int b)
46 {
47 y=a;
48 x=b;
49 memset(m,0,sizeof(m));
50 }
51 void init1()
52 {
53 for(int i=0; i<y; i++) m[i][i]=1;
54 }
55 friend matrix operator * (matrix a,matrix b)
56 {
57 matrix c;
58 c.init(a.y,b.x);
59 for(int i=0; i<a.y; i++)
60 {
61 for(int j=0; j<a.x; j++)
62 {
63 c.m[i][j]=0;
64 for(int k=0; k<b.x; k++)
65 {
66 c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%MOD;
67 }
68 }
69 }
70 return c;
71 }
72 friend matrix operator ^ (matrix a,int k)
73 {
74 matrix res;
75 res.init(a.y,a.x);
76 res.init1();
77 while(k)
78 {
79 if(k&1) res=res*a;
80 a=a*a;
81 k>>=1;
82 }
83 return res;
84 }
85 long long getsum()
86 {
87 long long res=0;
88 for(int i=0; i<y; i++)
89 for(int j=0; j<x; j++)
90 {
91 res=(res+m[i][j])%MOD;
92 }
93 return res;
94 }
95};
96matrix mat,ans;
97void cas_init()
98{
99 root=0;
100 s[root].init();
101 sind=1;
102}
103void ins(char str[])
104{
105 int i,j,len=strlen(str);
106 int ind=root;
107 for(i=0; i<len; i++)
108 {
109 j=hash[str[i]];
110 if(s[ind].next[j]==-1)
111 {
112 s[sind].init();
113 s[ind].next[j]=sind++;
114 }
115 ind=s[ind].next[j];
116 }
117 s[ind].count++;
118}
119void make_fail()
120{
121 int u,i,p,son;
122 head=0;
123 tail=1;
124 q[tail]=root;
125 while(head<tail)
126 {
127 head++;
128 u=q[head];
129 for(i=0; i<4; i++)
130 {
131 if(s[u].next[i]!=-1)
132 {
133 p=s[u].fail;
134 son=s[u].next[i];
135 while(p!=-1&&s[p].next[i]==-1)
136 p=s[p].fail;
137 if(u==root)
138 s[son].fail=root;
139 else s[son].fail=s[p].next[i];
140 if(s[s[son].fail].count)
141 s[son].count=1;
142 q[++tail]=son;
143 }
144 else//構trie圖
145 {
146 p=s[u].fail;
147 while(p!=-1&&s[p].next[i]==-1)
148 p=s[p].fail;
149 if(u==root) //傳遞傳遞
150 s[u].next[i]=root;
151 else s[u].next[i]=s[p].next[i];
152 }
153 }
154 }
155}
156void make_mats()
157{
158 mat.init(sind,sind);
159 ans.init(1,sind);
160 ans.m[0][0]=1;
161 int i,j,son;
162 for(i=0; i<sind; i++)
163 {
164 if(s[i].count) continue;
165 for(j=0; j<4; j++)
166 {
167 son=s[i].next[j];
168 if(s[son].count) continue;
169 mat.m[i][son]++;
170 }
171 }
172}
173int main()
174{
175 hash['A']=0;
176 hash['T']=1;
177 hash['G']=2;
178 hash['C']=3;
179 while(scanf("%d%d",&m,&n)!=EOF)
180 {
181 cas_init();
182 for(int i=0; i<m; i++)
183 {
184 scanf("%s",str);
185 ins(str);
186 }
187 make_fail();
188 make_mats();
189 ans=ans*(mat^n);
190 __int64 res;
191 res=ans.getsum();
192 printf("%I64d\n",res);
193
194 }
195 return 0;
196}
197
198