DNA Sequence
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 10868 | Accepted: 4146 |
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.
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.
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
题意：给出一组模式串求出给定长度的字符串的组合数，要满足不包含模式串。
sl:先将模式串建成一个自动机，（要把失配边加上）然后根据图构造出一个矩阵，求长度为k的字符串就相当于在自动机上走K步
n有2*1e9那么大不能用白书介绍的dp方法，想到离散数学，很容易知道，求长度为k的路径就是求矩阵的k次方，所以做下快速幂
然后把结果加起来就可以。
1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 #include<queue>
5 using namespace std;
6 typedef long long LL;
7 const int MAX = 200;
8 const int MOD = 100000;
9 char p[MAX];
10 LL map[MAX][MAX];
11 LL ans[MAX][MAX],sz;
12 LL z[MAX][MAX];
13 struct AC
14 {
15 int ch[MAX][MAX],val[MAX],f[MAX];
16 void init(){ sz=1; memset(ch,0,sizeof(ch)); memset(val,0,sizeof(val));}
17
18 int index(char c)
19 {
20 if(c=='A') return 0;
21 else if(c=='C') return 1;
22 else if(c=='G') return 2;
23 else return 3;
24 }
25
26 void insert(char *s)
27 {
28 int u = 0, n = strlen(s);
29 for(int i = 0; i < n; i++)
30 {
31 int c = index(s[i]);
32 if(!ch[u][c])
33 {
34 memset(ch[sz], 0, sizeof(ch[sz]));
35 val[sz] = 0;
36 ch[u][c] = sz++;
37 }
38 u = ch[u][c];
39 }
40 val[u] = 1;
41 }
42
43 void getfail()
44 {
45 queue<int> q;
46 f[0] = 0;
47 for(int c = 0; c < 4; c++)
48 {
49 int u = ch[0][c];
50 if(u) { f[u] = 0; q.push(u); }
51 }
52 while(!q.empty())
53 {
54 int r = q.front(); q.pop();
55 for(int c = 0; c < 4; c++) {
56 int u = ch[r][c];
57 if(!u) { ch[r][c] = ch[f[r]][c]; continue; }
58 q.push(u);
59 int v = f[r];
60 while(v && !ch[v][c]) v = f[v];
61 f[u] = ch[v][c];
62 val[u] |= val[f[u]];
63 // printf("%d ",val[u]);
64 }
65 }
66 }
67 };
68
69
70 void multiply(LL x[MAX][MAX],LL y[MAX][MAX])
71 {
72 for(int i=0;i<sz;i++)
73 {
74 for(int j=0;j<sz;j++)
75 {
76 z[i][j]=0;
77 for(int k=0;k<sz;k++)
78 z[i][j]=z[i][j]+x[i][k]*y[k][j];
79 z[i][j]%=MOD;
80 }
81 }
82 for(int i=0;i<sz;i++)
83 for(int j=0;j<sz;j++)
84 y[i][j]=z[i][j];
85 }
86 int main()
87 {
88 int n,m;
89 AC ac;
90 while(scanf("%d %d",&m,&n)==2)
91 {
92 ac.init();
93 for(int i=0;i<m;i++)
94 {
95 scanf("%s",p);
96 ac.insert(p);
97 }
98 ac.getfail();
99 memset(map,0,sizeof(map));
100 memset(ans,0,sizeof(ans));
101 for(int i=0;i<sz;i++)
102 {
103 if(!ac.val[i])
104 {
105 for(int j=0;j<4;j++)
106 {
107 if(!ac.val[ac.ch[i][j]])
108 map[i][ac.ch[i][j]]++;
109 }
110 }
111 }
112
113 for(int i=0;i<sz;i++) ans[i][i]=1;
114 while(n)
115 {
116 if(n & 1) multiply(map,ans);
117 multiply(map,map);
118 n>>=1;
119 }
120
121 LL res = 0;
122 for(int i=0;i<sz;i++) res=res+ans[0][i];
123 printf("%I64d ",res%MOD);
124 return 0;
125 }
126 }