DNA Sequence
Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 14758 Accepted: 5716 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 3ATACAGAASample Output
36
【分析】 之前做过的题。 建立一个AC自动机，然后把每个字符串的最后一位所在的节点标黑。（就是把mark变为1） 然后用AC自动机建立矩阵array[i][j]表示从i走到j的方案数，然后利用矩阵乘法的性质，用快速幂求出矩阵的M次幂即可。 代码依然丑：
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 #define Maxn 1010 9 #define LL long long 10 #define Mod 100000 11 12 struct node 13 { 14 int x,fail; 15 int son[6]; 16 bool mark; 17 }t[Maxn];int tot=0; 18 19 struct Matrix 20 { 21 LL a[110][110]; 22 }ay,ut; 23 24 void upd(int x) 25 { 26 t[x].mark=0; 27 memset(t[x].son,0,sizeof(t[x].son)); 28 } 29 30 Matrix h; 31 void clear(int id) 32 { 33 for(int i=0;i<=tot;i++) 34 for(int j=0;j<=tot;j++) 35 if(id==1) ay.a[i][j]=0; 36 else h.a[i][j]=0; 37 } 38 39 int m,n; 40 char s[Maxn]; 41 42 void read_trie() 43 { 44 scanf("%s",s+1); 45 int len=strlen(s+1); 46 int now=0; 47 for(int i=1;i<=len;i++) 48 { 49 int ind; 50 if(s[i]=='A') ind=1; 51 else if(s[i]=='T') ind=2; 52 else if(s[i]=='C') ind=3; 53 else ind=4; 54 if(!t[now].son[ind]) 55 { 56 t[now].son[ind]=++tot,upd(tot); 57 } 58 now=t[now].son[ind]; 59 if(i==len) t[now].mark=1; 60 } 61 } 62 63 queue q; 64 void build_AC() 65 { 66 while(!q.empty()) q.pop(); 67 q.push(0); 68 while(!q.empty()) 69 { 70 int now=q.front();q.pop(); 71 int f=t[now].fail; 72 for(int i=1;i<=4;i++) 73 { 74 if(t[now].son[i]) 75 { 76 q.push(t[now].son[i]); 77 t[t[now].son[i]].fail=now?t[f].son[i]:0; 78 if(t[t[t[now].son[i]].fail].mark) t[t[now].son[i]].mark=1; 79 } 80 else t[now].son[i]=t[f].son[i]; 81 if(t[t[now].son[i]].mark!=1) ay.a[now][t[now].son[i]]++; 82 } 83 } 84 } 85 86 Matrix mul(Matrix a,Matrix b) 87 { 88 clear(2); 89 for(int i=0;i<=tot;i++) 90 for(int j=0;j<=tot;j++) 91 for(int k=0;k<=tot;k++) 92 { 93 h.a[i][j]=(h.a[i][j]+a.a[i][k]*b.a[k][j])%Mod; 94 95 } 96 return h; 97 } 98 99 void qpow(int k)100 {101 while(k)102 {103 if(k&1) ut=mul(ut,ay);104 ay=mul(ay,ay);105 k>>=1;106 }107 }108 109 void init()110 {111 scanf("%d%d",&m,&n);112 tot=0;upd(0);113 for(int i=1;i<=m;i++)114 {115 read_trie();116 }117 clear(1);118 build_AC();119 for(int i=0;i<=tot;i++)120 for(int j=0;j<=tot;j++)121 ut.a[i][j]=i==j?1:0;122 123 qpow(n);124 LL ans=0;125 for(int i=0;i<=tot;i++) ans=(ans+ut.a[0][i])%Mod;126 printf("%I64d\n",ans);127 }128 129 int main()130 {131 init();132 return 0;133 }
以前的code：
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 8 const int Maxn=150; 9 const int Mod=(int)1e5; 10 char s[Maxn]; 11 int q[Maxn]; 12 long long ay[Maxn][Maxn],sum[Maxn][Maxn]; 13 int n,m,tot,len; 14 15 struct node 16 { 17 int son[6],cnt,fail,mark; 18 }t[Maxn]; 19 20 void floy() 21 { 22 tot=0; 23 for(int i=1;i<=Maxn;i++) 24 { 25 t[i].cnt=0;t[i].mark=0; 26 for(int j=1;j<=5;j++) t[i].son[j]=0; 27 } 28 memset(q,0,sizeof(q)); 29 } 30 31 void read_trie() 32 { 33 tot=0; 34 int i,j; 35 scanf("%d%d",&m,&n); 36 for(i=1;i<=m;i++) 37 { 38 int x,ind; 39 scanf("%s",s+1); 40 len=strlen(s+1); 41 x=0; 42 for(j=1;j<=len;j++) 43 { 44 if(s[j]=='A') ind=1; 45 else if(s[j]=='C') ind=2; 46 else if(s[j]=='T') ind=3; 47 else if(s[j]=='G') ind=4; 48 if(!t[x].son[ind]) t[x].son[ind]=++tot; 49 x=t[x].son[ind]; 50 t[x].cnt++; 51 if(j==len) t[x].mark=1; 52 } 53 } 54 } 55 56 void build_AC() 57 { 58 int i,j,x,y; 59 q[++q[0]]=0; 60 //for(i=1;i<=4;i++) 61 //if(t[0].son[i]) q[++q[0]]=t[0].son[i]; 62 for(i=1;i<=q[0];i++) 63 { 64 x=q[i]; 65 y=t[x].fail; 66 for(j=1;j<=4;j++) 67 { 68 if(t[x].son[j]) 69 { 70 //t[t[x].son[j]].fail=t[y].son[j]; 71 q[++q[0]]=t[x].son[j]; 72 t[t[x].son[j]].fail=x?t[y].son[j]:x; 73 if(t[t[t[x].son[j]].fail].mark) t[t[x].son[j]].mark=1; 74 } 75 else t[x].son[j]=t[y].son[j]; 76 if(!t[t[x].son[j]].mark) ay[x][t[x].son[j]]++; 77 } 78 } 79 } 80 81 void MatrixMult(long long a[Maxn][Maxn],long long b[Maxn][Maxn]) 82 { 83 int i,j,k; 84 long long c[Maxn][Maxn]; 85 memset(c,0,sizeof(c)); 86 for(i=0;i<=tot;i++) 87 for(j=0;j<=tot;j++) 88 for(k=0;k<=tot;k++) 89 c[i][j]+=a[i][k]*b[k][j]; 90 for(i=0;i<=tot;i++) 91 for(j=0;j<=tot;j++) 92 a[i][j]=c[i][j]%Mod; 93 } 94 95 long long MatrixPow(int k) 96 { 97 int i,j; 98 for(i=0;i<=tot;i++) 99 for(j=0;j<=tot;j++)100 sum[i][j]=(i==j);101 while(k)102 {103 if(k&1) MatrixMult(sum,ay);104 MatrixMult(ay,ay);105 k>>=1;106 }107 long long ans=0;108 for(i=0;i<=tot;i++) ans+=sum[0][i];109 return ans%Mod;110 }111 112 int main()113 {114 floy();115 read_trie();116 build_AC();117 printf("%I64d\n",MatrixPow(n));118 return 0;119 }
2016-06-23 16:22:32