DNA Sequence

 

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.

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.

An integer, the number of DNA sequences, mod 100000.

4 3

AT

AC

AG

AA

36
　　
思路是这样的：把所有病毒片段放入AC自动机中，建立fail数组。如果一个状态的fail为病毒节点，则他自己也为病毒节点。最后按边建矩阵，快速幂。

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <queue>

 using namespace std;

 const int maxn=;

 const int mod=;

 typedef unsigned long long ull;

 struct Matrix{

     int n;

     ull mat[maxn][maxn];

     Matrix(int n_,int on=){

         n=n_;memset(mat,,sizeof(mat));

         if(on)for(int i=;i<=n;i++)mat[i][i]=;

     }

     Matrix operator *(Matrix a){

         Matrix ret(n);

         unsigned long long l;

         for(int i=;i<=n;i++)

             for(int k=;k<=n;k++){

                 l=mat[i][k];

                 for(int j=;j<=n;j++)

                     (ret.mat[i][j]+=l*a.mat[k][j]%mod)%=mod;

             }

         return ret;

     }

     Matrix operator ^(long long k){

         Matrix ret(n,);

         while(k){

             if(k&)

                 ret=ret**this;

             k>>=;

             *this=*this**this;

         }

         return ret;

     }

 };

 struct AC_automation{

     bool tag[maxn];

     int cnt,rt,ch[maxn][],fail[maxn];

     AC_automation(){

         memset(tag,,sizeof(tag));

         memset(fail,,sizeof(fail));

         memset(ch,,sizeof(ch));cnt=rt=;

     }

     int ID(char c){

         if(c=='A')return ;

         else if(c=='C')return ;

         else if(c=='G')return ;

         else return ;

     }

     void Insert(char *s){

         int len=strlen(s),p=rt;

         for(int i=;i<len;i++)

             if(ch[p][ID(s[i])])

                 p=ch[p][ID(s[i])];

             else

                 p=ch[p][ID(s[i])]=++cnt;

         tag[p]=true;

     }

     void Build(){

         queue<int>q;

         for(int i=;i<;i++)

             if(ch[rt][i])

                 fail[ch[rt][i]]=rt,q.push(ch[rt][i]);

             else

                 ch[rt][i]=rt;

         while(!q.empty()){

             int x=q.front();q.pop();

             for(int i=;i<;i++)

                 if(ch[x][i]){

                     fail[ch[x][i]]=ch[fail[x]][i];

                     tag[ch[x][i]]|=tag[fail[ch[x][i]]];

                     q.push(ch[x][i]);

                 }

                 else

                     ch[x][i]=ch[fail[x]][i];

         }

     }

     void Solve(int k){

         Matrix A(cnt);

         for(int i=;i<=cnt;i++)

             for(int j=;j<;j++)

                 if(!tag[i]&&!tag[ch[i][j]])

                     A.mat[ch[i][j]][i]+=;

         A=A^k;

         long long ans=;

         for(int i=;i<=cnt;i++)

             ans+=A.mat[i][];

         printf("%lld\n",ans%mod);

     }

 }ac;

 char s[maxn];

 int main(){

 #ifndef ONLINE_JUDGE

     //freopen("","r",stdin);

     //freopen("","w",stdout);

 #endif

     int tot,n;

     scanf("%d%d",&tot,&n);

     while(tot--){

         scanf("%s",s);

         ac.Insert(s);

     }

     ac.Build();

     ac.Solve(n);

     return ;

 }