[poj2778]DNA Sequence(AC自动机+矩阵快速幂)

题意：有m种DNA序列是有疾病的，问有多少种长度为n的DNA序列不包含任何一种有疾病的DNA序列。（仅含A,T,C,G四个字符）

解题关键：AC自动机，实际上就是一个状态转移图，注意能少取模就少取模，尤其是在快速幂的时候，消耗时间极其巨大，此题效率差10倍。

先+=在进行取模，两者分开，也可以快1倍。

按照AC自动机建立邻接矩阵，其中不含病毒模式串的位置可以到达，

其中上图矩阵为：

2 1 0 0 1

2 1 1 0 0

1 1 0 1 1

2 1 0 0 1

去掉病毒结点之后，变为

2 1

转移方程：$dp[u] = sumlimits_{v - > u} {dp[v]} $

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<cstdlib>
  5 #include<cstring>
  6 #include<iostream>
  7 #include<queue>
  8 using namespace std;
  9 typedef long long ll;
 10 const int N=4;
 11 const int MAXN=101;
 12 struct mat{
 13     ll m[101][101];
 14 };
 15 ll m,n;
 16 ll mod=100000;
 17 struct Trie{
 18     int Next[MAXN][N],Fail[MAXN],root,tot;
 19     bool End[MAXN];
 20     int newnode(){
 21         for(int i=0;i<N;i++) Next[tot][i]=-1;
 22         End[tot++]=false;
 23         return tot-1;
 24     }
 25     void init(){
 26         tot=0;
 27         root=newnode();
 28     }
 29     void insert(char buf[]){
 30         int len=strlen(buf),now=root,k;
 31         for(int i=0;i<len;i++){
 32             if(buf[i]=='A') k=0;
 33             else if(buf[i]=='G') k=1;
 34             else if(buf[i]=='C') k=2;
 35             else k=3;
 36             if(Next[now][k]==-1)  Next[now][k]=newnode();
 37             now=Next[now][k];
 38         }
 39         End[now]=true;
 40     }
 41     void build(){
 42         queue<int>que;
 43         Fail[root]=root;
 44         for(int i=0;i<N;i++){ 
 45             if(Next[root][i]==-1) Next[root][i]=root;
 46             else{
 47                 Fail[Next[root][i]]=root;
 48                 que.push(Next[root][i]);
 49             }
 50         } 
 51         while(!que.empty()){
 52             int now=que.front();
 53             que.pop();
 54             if(End[Fail[now]]) End[now]=true;
 55             for(int i=0;i<N;i++){
 56                 if(Next[now][i]==-1) Next[now][i]=Next[Fail[now]][i];
 57                 else{
 58                     Fail[Next[now][i]]=Next[Fail[now]][i];
 59                     que.push(Next[now][i]);
 60                 }
 61             }
 62         }
 63     }
 64     mat get_mat(int len){
 65         mat B={0};
 66         for(int i=0;i<len;i++){
 67             for(int j=0;j<N;j++){
 68                 if(End[Next[i][j]]==false) B.m[i][Next[i][j]]++;//不能直接置1 
 69             }
 70         }
 71         return B;
 72     }
 73 };
 74 
 75 mat mul(mat &A,mat &B,int len){
 76     mat C={0};
 77     for(int i=0;i<len;i++){
 78         for(int j=0;j<len;j++){
 79             for(int k=0;k<len;k++){
 80                 C.m[i][j]+=A.m[i][k]*B.m[k][j];
 81             }
 82             C.m[i][j]%=mod;
 83         }
 84     }
 85     return C;
 86 }
 87 
 88 mat pow(mat A,ll n,int len){
 89     mat B={0};
 90     for(int i=0;i<len;i++) B.m[i][i]=1;
 91     while(n){
 92         if(n&1) B=mul(B,A,len);
 93         A=mul(A,A,len);
 94         n>>=1;
 95     }
 96     return B;
 97 }
 98 
 99 Trie ac;
100 char buf[10];
101 int main(){
102     while(scanf("%lld%lld",&m,&n)!=EOF){
103         ac.init();
104         for(int i=0;i<m;i++){
105             scanf("%s",buf);
106             ac.insert(buf);
107         }
108         ac.build();
109         mat B=ac.get_mat(ac.tot);
110         B=pow(B,n,ac.tot);
111         ll res=0;
112         for(int i=0;i<ac.tot;i++){
113             res+=B.m[0][i];
114         }
115         printf("%lld
",res%mod);
116     }
117     return 0;
118 }