题意：
给p个模式串，求长度为m的所有串中不含任意模式串的串的个数。
分析：
这道题不让求模，所以要用高精度，但是在矩阵乘法里用高精度花销太大，好在长度m不大，可以一步一步dp出来。在dp里加个高精度是个很有意思的事情，，详见代码。
代码：
//poj 1625#include <iostream>#include <queue>using namespace std;int map[300];int n,m,p,len;char s[64];int alphabet_len,index;queue<int> Q; int dp[51][110][110]; struct Node{int s[64],fail;bool word;}a[64*64];void insert(int h,int k){if(k==len){a[h].word=true;return ;}int p=map[s[k]+128];if(!a[h].s[p])a[h].s[p]=++index;insert(a[h].s[p],k+1);}void build_AC_Automation(){while(!Q.empty()) Q.pop();Q.push(0);while(!Q.empty()){int h=Q.front();Q.pop();for(int k=0;k<alphabet_len;++k)if(a[h].s[k]){Q.push(a[h].s[k]);if(h) a[a[h].s[k]].fail=a[a[h].fail].s[k];if(a[a[a[h].s[k]].fail].word==true)a[a[h].s[k]].word=true;}elsea[h].s[k]=a[a[h].fail].s[k];}}void add(int *a,int *b){int p,i;for(p=i=0;i<100;++i){a[i]=a[i]+b[i]+p;p=a[i]/10;a[i]%=10;}}void print(int *a){int i;for(i=100;i>=0;–i)if(a[i]) break;if(i<0)printf("0\n");else{for(int j=i;j>=0;–j)printf("%d",a[j]);printf("\n");}}int main(){scanf("%d%d%d",&n,&m,&p);getchar();gets(s);memset(map,-1,sizeof(map));alphabet_len=0;for(int i=0;s[i]!='\0';++i){int ss=s[i]+128;if(map[ss]==-1)map[ss]=alphabet_len++;}memset(a,0,sizeof(a));index=0;while(p–){gets(s);len=strlen(s);insert(0,0);}build_AC_Automation();memset(dp,0,sizeof(dp));int i,j,k;for(i=0;i<=index;++i)if(a[i].word==false)dp[0][i][0]=1;for(k=1;k<=m;++k)for(i=0;i<=index;++i)for(j=0;j<alphabet_len;++j){int next_i=a[i].s[j];if(a[i].word==false&&a[next_i].word==false)add(dp[k][i],dp[k-1][next_i]);}print(dp[m][0]);return 0;}
只有经历过地狱般的折磨，才有征服天堂的力量。
