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>
16
using namespace std;
17
#define maxn 105
18
#define MOD 100000
19
int n,m;
20
int root,head,tail,sind;
21
int q[maxn*maxn];
22
char str[15];
23
int hash[300];
24
struct node
25![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
26
int next[4];
27
int count,fail;
28
void init()
29![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
30
memset(next,-1,sizeof(next));
31
fail=-1;
32
count=0;
33
}
34
} s[maxn];
35
struct matrix
36![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
37
int y,x;
38
long long m[maxn][maxn];
39
void init()
40![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
41
memset(m,0,sizeof(m));
42
y=0;
43
x=0;
44
}
45
void init(int a,int b)
46![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
47
y=a;
48
x=b;
49
memset(m,0,sizeof(m));
50
}
51
void init1()
52![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
53
for(int i=0; i<y; i++) m[i][i]=1;
54
}
55
friend matrix operator * (matrix a,matrix b)
56![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
57
matrix c;
58
c.init(a.y,b.x);
59
for(int i=0; i<a.y; i++)
60![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
61
for(int j=0; j<a.x; j++)
62![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
63
c.m[i][j]=0;
64
for(int k=0; k<b.x; k++)
65![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
74
matrix res;
75
res.init(a.y,a.x);
76
res.init1();
77
while(k)
78![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
79
if(k&1) res=res*a;
80
a=a*a;
81
k>>=1;
82
}
83
return res;
84
}
85
long long getsum()
86![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
87
long long res=0;
88
for(int i=0; i<y; i++)
89
for(int j=0; j<x; j++)
90![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
91
res=(res+m[i][j])%MOD;
92
}
93
return res;
94
}
95
};
96
matrix mat,ans;
97
void cas_init()
98![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
99
root=0;
100
s[root].init();
101
sind=1;
102
}
103
void ins(char str[])
104![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
105
int i,j,len=strlen(str);
106
int ind=root;
107
for(i=0; i<len; i++)
108![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
109
j=hash[str[i]];
110
if(s[ind].next[j]==-1)
111![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
112
s[sind].init();
113
s[ind].next[j]=sind++;
114
}
115
ind=s[ind].next[j];
116
}
117
s[ind].count++;
118
}
119
void make_fail()
120![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
121
int u,i,p,son;
122
head=0;
123
tail=1;
124
q[tail]=root;
125
while(head<tail)
126![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
127
head++;
128
u=q[head];
129
for(i=0; i<4; i++)
130![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
131
if(s[u].next[i]!=-1)
132![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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
}
156
void make_mats()
157![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
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![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
164
if(s[i].count) continue;
165
for(j=0; j<4; j++)
166![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
167
son=s[i].next[j];
168
if(s[son].count) continue;
169
mat.m[i][son]++;
170
}
171
}
172
}
173
int main()
174![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
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![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
181
cas_init();
182
for(int i=0; i<m; i++)
183![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](/Images/OutliningIndicators/InBlock.gif)
194
}
195
return 0;
196
}
197![](/Images/OutliningIndicators/None.gif)
198![](/Images/OutliningIndicators/None.gif)