这题要写的东西很多，以至于我不知道从哪里开始写了= =。
总之要正确理解AC自动机中的状态转移。时间比较晚了，早点回去...
我要注意的地方就是正确理解fail指针的作用。在失配时，fail指针如果走向的是一个病毒节点那么改节点的转移也是病毒节点。不能转移！
另外要注意的就是mod十分的耗时间啊！两次TLE都是出于此....
总之是一道好题
#include<iostream>
#include<cstdio>
#include<string.h>
#define kind 4
#define MAX 111
using namespace std;struct node
{int fail,flag;int next[4];void init(){fail=flag=0;memset(next,0,sizeof(next));}
}Tire[MAX];__int64 matrix[MAX][MAX];
int root,allocp;
__int64 tot[MAX][MAX];int index(char c)
{if( c=='A' )return 0;if( c=='C' )return 1;if( c=='G' )return 2;if( c=='T' )return 3;
}void init()
{root=allocp=0;Tire[root].init();memset( matrix,0,sizeof(matrix) );memset(tot,0,sizeof(tot));
}void Insert( char *s ){int i=0,k;int p=root;while( s[i] ){k=index(s[i++]);if( !Tire[p].next[k] ){Tire[++allocp].init();Tire[p].next[k]=allocp;}else if( Tire[p].flag )return ;p=Tire[p].next[k];}Tire[p].flag++;
}void build_ac_automation()
{int queue[111];int head,foot;head=foot=0;queue[foot++]=root;while( head<foot ){int cur=queue[head++];for( int i=0;i<kind;i++ ){int son=Tire[cur].next[i];if( son ){//if have nextint p=Tire[cur].fail;if( cur==root ) Tire[son].fail=root;else Tire[son].fail=Tire[p].next[i];if( Tire[Tire[son].fail].flag )Tire[son].flag++;queue[foot++]=son;}else{int p=Tire[cur].fail;if( cur==root ) Tire[cur].next[i]=root;else Tire[cur].next[i]=Tire[p].next[i];}}}
}void set_matrix()
{int son;for( int p=0;p<=allocp;p++ ){if( Tire[p].flag )continue;for( int i=0;i<kind;i++ ){son=Tire[p].next[i];if( Tire[son].flag==0 )matrix[p][son]++;}}/*for( int i=0;i<=allocp;i++ ){for( int j=0;j<=allocp;j++ )printf( "%d",matrix[i][j] );printf( "\n" );}*/
}__int64 res[MAX][MAX],temp[MAX][MAX];void matrixMult( __int64 a[][MAX],__int64 b[][MAX] )
{__int64 kk[MAX][MAX];memset( kk,0,sizeof(kk) );for( int i=0;i<=allocp;i++ )for( int j=0;j<=allocp;j++ )for( int k=0;k<=allocp;k++ )kk[i][j]+=a[i][k]*b[k][j];for( int i=0;i<=allocp;i++ )for( int j=0;j<=allocp;j++ )a[i][j]=kk[i][j]%100000;
}__int64 matrix_Power(int n)
{memset( res,0,sizeof(res) );memset( temp,0,sizeof(temp) );int ret=0;for( int i=0;i<=allocp;i++ ){res[i][i]=1;for( int j=0;j<=allocp;j++ )temp[i][j]=matrix[i][j];}for( int p=0;p<32;p++ ){if( n&(1<<p) )matrixMult( res,temp );matrixMult( temp,temp );}for( int i=0;i<=allocp;i++ )ret+=res[0][i];return ret%100000;
}int main(){//freopen( "my.out","w",stdout );int m,n;while( scanf("%d%d",&m,&n)!=EOF ){init();char str[22];while( m-- ){scanf("%s",&str);Insert(str);}build_ac_automation();set_matrix();__int64 sum=matrix_Power(n);printf( "%d\n",sum%100000 );}return 0;
}