题意：
给m个模式串，问长度为n的所有串中不含所有模式串的串有几个。
分析：
构造完ac自动机后将自动机转换为状态转移矩阵，mat[i][j]表示一步从状态i到状态j的方法数。最后用矩阵幂加速。ps:求模运算很慢，尽量放在for循环外层。
代码：
//poj 2778
//sep9
#include <iostream>
#include <queue>
using namespace std;
typedef __int64 LL;
const int mod=100000;struct node
{int s[4],fail;bool word;
}a[128];
struct MAT
{LL v[128][128];
}mat,ans;char segment[16];
int len,code[100];
int index;
queue<int> Q;void build_trie(int h,int k)
{if(k==len){a[h].word=true;return ;} int p=code[segment[k]];if(!a[h].s[p]) a[h].s[p]=++index;build_trie(a[h].s[p],k+1);
}
MAT mul(MAT x,MAT y)
{MAT z;memset(z.v,0,sizeof(z.v));for(int i=0;i<=index;++i)for(int j=0;j<=index;++j){for(int k=0;k<=index;++k)z.v[i][j]+=x.v[i][k]*y.v[k][j];z.v[i][j]%=mod;}return z;
}
void build_AC_Automation()
{int h,i;while(!Q.empty()) Q.pop();Q.push(0);while(!Q.empty()){int h=Q.front();Q.pop();for(i=0;i<4;++i)if(a[h].s[i]){Q.push(a[h].s[i]);if(h) a[a[h].s[i]].fail=a[a[h].fail].s[i];if(a[a[a[h].s[i]].fail].word==true) a[a[h].s[i]].word=true;}else if(h)a[h].s[i]=a[a[h].fail].s[i];}
}
void build_matrix()
{memset(mat.v,0,sizeof(mat.v));for(int i=0;i<=index;++i)for(int j=0;j<4;++j)if(a[i].word==false&&a[a[i].s[j]].word==false)++mat.v[i][a[i].s[j]];
}
void pow_matrix(int n)
{memset(ans.v,0,sizeof(ans.v)); for(int i=0;i<=index;++i) ans.v[i][i]=1;while(n){if(n&1) ans=mul(ans,mat);mat=mul(mat,mat);n>>=1;}
}int main()
{int m,n;code['A']=0;code['C']=1;code['T']=2;code['G']=3;scanf("%d%d",&m,&n);index=0;memset(a,0,sizeof(a));while(m--){scanf("%s",segment);len=strlen(segment);build_trie(0,0);}build_AC_Automation();build_matrix();pow_matrix(n); LL sum=0;for(int i=0;i<=index;++i)sum+=ans.v[0][i];sum%=mod;printf("%I64d",sum);return 0;
}