题目链接：
解析：AC自己主动机 + 高精度 + 简单DP。
字符有可能会超过128。用map映射一下就可以。
中间的数太大。得上高精度。
用矩阵高速幂会超时，简单的DP就能解决时间的问题。
AC代码：
#include #include #include #include #include #include
a[i]:0)+((i < b.len)?
b.a[i]:0); res.a[i+1] += res.a[i]/mod; res.a[i] %= mod; } if(res.a[res.len] > 0)res.len++; return res; } BigInt operator *(const BigInt &b)const { BigInt res; for(int i = 0; i < len;i++) { int up = 0; for(int j = 0;j < b.len;j++) { int temp = a[i]*b.a[j] + res.a[i+j] + up; res.a[i+j] = temp%mod; up = temp/mod; } if(up != 0) res.a[i + b.len] = up; } res.len = len + b.len; while(res.a[res.len - 1] == 0 &&res.len > 1)res.len--; return res; } void output() { printf("%d",a[len-1]); for(int i = len-2;i >=0 ;i--) printf("%04d",a[i]); printf("\n"); } }; char buf[1010]; BigInt dp[2][110]; Trie ac; int main() { // freopen("in.txt","r",stdin); while(scanf("%d%d%d",&N,&M,&P)==3) { gets(buf); gets(buf); mp.clear(); int len = strlen(buf); for(int i = 0;i < len;i++) mp[buf[i]]=i; ac.init(); for(int i = 0;i < P;i++) { gets(buf); ac.insert(buf); } ac.build(); Matrix a= ac.getMatrix(); int now = 0; dp[now][0] = 1; for(int i = 1;i < a.n;i++) dp[now][i] = 0; for(int i = 0;i < M;i++) { now^=1; for(int j = 0;j < a.n;j++) dp[now][j] = 0; for(int j = 0;j < a.n;j++) for(int k = 0;k < a.n;k++) if(a.mat[j][k] > 0) dp[now][k] = dp[now][k]+dp[now^1][j]*a.mat[j][k]; } BigInt ans = 0; for(int i = 0;i < a.n;i++) ans = ans + dp[now][i]; ans.output(); } return 0; }