POJ 2778 DNA Sequence

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
const int mod=100000;
struct matrix
{
    int a[100][100];
    int N;
    matrix(int x):N(x){memset(a,0,sizeof a);}
    int* operator [] (int i){return a[i];}
    matrix operator * (matrix & B)
    {
        matrix ret(N);
        for(int i=0;i<N;++i)for(int k=0;k<N;++k)if(a[i][k])for(int j=0;j<N;++j)ret[i][j]=(1LL*a[i][k]*B[k][j]+ret[i][j])%mod;
        return ret;
    }
};
matrix quick_pow(matrix a,int n)
{
    matrix ret(a.N);
    for(int i=0;i<a.N;++i)ret[i][i]=1;
    while(n)
    {
        if(n&1)ret=ret*a;
        a=a*a;
        n>>=1;
    }
    return ret;
}
struct Trie
{
    int ch[100][4],val[100],fail[100],sz;
    int newnode(){memset(ch[sz],-1,sizeof ch[sz]);val[sz]=0;return sz++;}
    void init(){sz=0;newnode();}
    int idx(char ch)
    {
        if(ch=='A') return 0;
        else if(ch=='C') return 1;
        else if(ch=='G') return 2;
        else if(ch=='T') return 3;
    }
    void insert(char s[],int v)
    {
        int u;for(u=0;*s;++s){if(ch[u][idx(*s)]==-1)ch[u][idx(*s)]=newnode();u=ch[u][idx(*s)];}
        val[u]=v;
    }
    void build()
    {
        queue<int>q;
        for(int i=0;i<4;++i)
        {
            if(ch[0][i]==-1)ch[0][i]=0;
            else {fail[ch[0][i]]=0;q.push(ch[0][i]);}
        }
        while(!q.empty())
        {
            int u=q.front();q.pop();
            if(val[fail[u]])val[u]=1;
            for(int i=0;i<4;++i)
            {
                if(ch[u][i]==-1)ch[u][i]=ch[fail[u]][i];
                else{fail[ch[u][i]]=ch[fail[u]][i];q.push(ch[u][i]);}
            }
        }
    }
    void query(int L)
    {
        matrix A(sz);
        for(int i=0;i<sz;++i)for(int j=0;j<4;++j)if(val[ch[i][j]]==0)++A[ch[i][j]][i];
        A=quick_pow(A,L);
        int ret=0;
        for(int i=0;i<sz;++i)ret=(ret+A.a[i][0])%mod;
        printf("%d
",ret);
    }
}T;
int main()
{
    //freopen("Input.txt","r",stdin);
    int _m,_n;char s[15];
    while(~scanf("%d%d",&_m,&_n))
    {
        T.init();
        for(int i=1;i<=_m;++i)scanf("%s",s),T.insert(s,1);
        T.build();
        T.query(_n);
    }
}