题意：容易理解...
思路：这个之前做的poj 1625差不多，只是1625是属于大数的，用矩阵乘法不好做（会爆栈），直接DP就行，这一题需要用到矩阵乘法来提高程序运行效率，要注意的地方就是取模运算挺慢的所以要尽量减少这种运算，开始的时候我一直RE，原来是因为m=0的时候没有考虑到。在做这题之前建议先把1625做了，这两道题最重要的还是要理解Trie图的建立方法、目的、原理。其实我还想说的就是我们写代码的时候还是要注意细节问题，在平时我们要多多积累，真正比赛的时候才不会犯一些小错误，比如这题中矩阵乘法时，我开始准备直接开二维数组来保存矩阵的，但是后来发现这样弄的话对于矩阵的计算不好算，然后学着大牛的写法，先建立一个结构体，然后结构体里面开设一个二维数组，这样的话我们进行函数调用时侯不会改变节点的值。具体看代码实现：
这道题我参考的资料：http://hi.baidu.com/ccsu_010/item/7847a3c17f6fe2bc0d0a7b89挺好的
poj 1625我的博客：http://www.cnblogs.com/jiangjing/archive/2013/05/02/3055431.html
代码实现：
#include<iostream> #include<string.h> #include<queue> #include<algorithm> using namespace std; struct node{ __int64 flag; __int64 fail; __int64 next[4]; void init() { flag=0; fail=0; memset(next,0,sizeof(next)); } }s[101]; struct yun{ __int64 num[101][101];//用来保存矩阵 }; struct yun a,b; __int64 n,m,tot; void ca()//初始化 { tot=0; s[0].init(); } int hash(char temp) { if(temp=='A') return 0; else if(temp=='C') return 1; else if(temp=='G') return 2; else return 3; } void insert(char *str)//建立字典树 { __int64 index,p=0; for(;*str!='\0';str++) { index=hash(*str); if(s[p].next[index]==0) { s[++tot].init(); s[p].next[index]=tot; } p=s[p].next[index]; } s[p].flag=1; } void AC_tree()//建立Trie图 { __int64 p,cur,son,i,kao; queue<int>Q; s[0].fail=0; Q.push(0); while(!Q.empty()) { p=Q.front(); Q.pop(); if(s[p].flag) continue; for(i=0;i<4;i++) { son=s[p].next[i]; if(son!=0) { if(p==0) s[son].fail=0; else { cur=s[p].fail; while(cur!=0&&s[cur].next[i]==0) cur=s[cur].fail; s[son].fail=s[cur].next[i]; } if(s[s[son].fail].flag==1) s[son].flag=1; if(s[son].flag==0&&s[p].flag==0) a.num[p][son]++; Q.push(son); } else { kao=s[s[p].fail].next[i]; s[p].next[i]=kao; if(s[kao].flag==0&&s[p].flag==0) a.num[p][kao]++; } } } } struct yun xiangcheng(struct yun c,struct yun d)//矩阵相乘 { __int64 i,j,k; struct yun e; for(i=0;i<=tot;i++) for(j=0;j<=tot;j++) { e.num[i][j]=0; for(k=0;k<=tot;k++) { e.num[i][j]=e.num[i][j]+c.num[i][k]*d.num[k][j]; if(e.num[i][j]>=100000) e.num[i][j]=e.num[i][j]%100000; } } return e; } void solve()//快速幂 { __int64 sum=0; __int64 i,j; for(i=0;i<=tot;i++) for(j=0;j<=tot;j++) b.num[i][j]=a.num[i][j]; m=m-1; while(m) { if(m%2==1) b=xiangcheng(b,a); a=xiangcheng(a,a); m=m/2; } for(i=0;i<=tot;i++) { sum=sum+b.num[0][i]; if(sum>=100000) sum=sum%100000; } printf("%I64d\n",sum); } int main() { char str[10]; while(scanf("%I64d%I64d",&n,&m)!=EOF) { getchar(); ca(); memset(a.num,0,sizeof(a.num)); while(n--) { scanf("%s",str); insert(str); } if(m==0)//这里需要注意下 { printf("%d\n",1); continue; } AC_tree(); solve(); } return 0; }