poj2778之AC自動機+矩陣快速冪

DNA Sequence
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 10171   Accepted: 3824

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首先要很蛋疼的說下我這個代碼無論怎麼樣都只能跑到100+ms,跑不到排名上的幾十ms甚至0ms,如果介意請無視，如果有大神能指出優化之處不勝感激
 

#include<iostream>   
#include<cstdio>   
#include<cstdlib>   
#include<cstring>   
#include<string>   
#include<queue>   
#include<algorithm>   
#include<map>   
#include<iomanip>   
#define INF 99999999   
using namespace std;  
  
const int MAX=100+10;//最大節點數    
const int mod=100000;  
__int64 array[MAX][MAX],sum[MAX][MAX];//進行矩陣乘法的初始矩陣和結果矩陣    
int n,m,size;//size表示節點個數   
char s[15];  
int Map[MAX];//映射A,C,G,T = 0,1,2,3   
  
struct TrieNode{  
    int id;//表示該節點的序號   
    bool mark;//標記是否是單詞   
    TrieNode *fail,*next[4];//失敗指針和下一個節點    
}*root,Node[MAX];  
  
TrieNode *New_TrieNode(){  
    memset(&Node[size],0,sizeof(TrieNode));  
    Node[size].id=size;  
    return &Node[size++];  
}  
  
void InsertNode(char *a){  
    TrieNode *p=root;  
    while(*a){  
        if(!p->next[Map[*a]])p->next[Map[*a]]=New_TrieNode();  
        p=p->next[Map[*a]];  
        ++a;  
    }  
    p->mark=true;  
}  
  
void Build_AC(){//建立AC自動機並且構造初始矩陣array    
    memset(array,0,sizeof array);  
    TrieNode *p=root,*next;  
    queue<TrieNode *>q;  
    q.push(root);  
    while(!q.empty()){  
        p=q.front();  
        q.pop();  
        for(int i=0;i<4;++i){  
            if(p->next[i]){  
                next=p->fail;  
                while(next && !next->next[i])next=next->fail;  
                p->next[i]->fail=next?next->next[i]:root;  
                if(p->next[i]->fail->mark)p->next[i]->mark=true;//防止ACG,AC這種一個病毒串的前綴是另一個病毒串的情況    
                q.push(p->next[i]);  
            }else p->next[i]=(p == root)?root:p->fail->next[i];//從這個點狀態可以遞推到失敗指針節點的下一個節點狀態    
            if(!p->next[i]->mark)++array[p->id][p->next[i]->id];//表示下一個狀態不是病毒串,則可以到達    
        }  
    }  
}  
  
void MatrixMult(__int64 a[MAX][MAX],__int64 b[MAX][MAX]){  
    __int64 c[MAX][MAX]={0};  
    for(int i=0;i<size;++i){  
        for(int j=0;j<size;++j){  
            for(int k=0;k<size;++k){  
                c[i][j]+=a[i][k]*b[k][j];  
            }  
        }  
    }  
    for(int i=0;i<size;++i){  
        for(int j=0;j<size;++j)a[i][j]=c[i][j]%mod;  
    }  
}  
  
__int64 MatrixPow(int k){  
    for(int i=0;i<size;++i){  
        for(int j=0;j<size;++j)sum[i][j]=(i == j);//單位矩陣    
    }  
    while(k){  
        if(k&1)MatrixMult(sum,array);//sum=sum*array;   
        MatrixMult(array,array);//array=array*array;   
        k>>=1;  
    }  
    __int64 ans=0;  
    for(int i=0;i<size;++i)ans+=sum[0][i];//從0狀態到達其他狀態的所有總和   
    return ans%mod;   
}  
  
int main(){  
    Map['A']=0,Map['C']=1,Map['G']=2,Map['T']=3;  
    while(scanf("%d%d",&m,&n)!=EOF){  
        size=0;//節點個數初始化為0    
        root=New_TrieNode();//創建根節點   
        for(int i=0;i<m;++i){  
            scanf("%s",s);  
            InsertNode(s);   
        }  
        Build_AC();  
        printf("%I64d\n",MatrixPow(n));  
    }  
    return 0;  
}