广告：#include <stdio.h>int main(){puts(“转载请注明出处[vmurder]谢谢”);puts(“网址：blog.csdn.net/vmurder/article/details/44003109”);}题解：
建立AC自动机的过程可以改为KMP。 反正单串233。
代码：;int n,m,p;struct MRX{int x[T][T];}Ini,Std,Trs,E;MRX operator * (const MRX &A,const MRX &B){MRX C=E;int i,j,k;for(i=0;i<T;i++)for(j=0;j<T;j++)for(k=0;k<T;k++)(C.x[i][j]+=(long long)A.x[i][k]*B.x[k][j]%p)%=p;return C;}MRX power(MRX X,int p){MRX Ans=Std;while(p){if(p&1)Ans=Ans*X;X=X*X,p>>=1;}return Ans;}struct ACAUTO{int son[T][T],cnt;char src[T];void build_Trie(){scanf(“%s”,src);int i,x=0,alp;for(i=0;src[i];i++){alp=src[i]-‘0’;if(!son[x][alp])son[x][alp]=++cnt;x=son[x][alp];}}queue<int>q;int fail[T];void build_Fail(){while(!q.empty())q.pop();q.push(1);int i,u,v;while(!q.empty()){u=q.front(),q.pop();for(i=0;i<10;i++){if(v=son[u][i]){if(u)fail[v]=son[fail[u]][i];else fail[v]=1;q.push(v);}else son[u][i]=son[fail[u]][i];}}}void build_Mrx(){int i,j,k;for(i=0;i<cnt;i++)for(j=0;j<10;j++)Trs.x[son[i][j]][i]++;}}acauto;int main(){freopen(“test.in”,”r”,stdin);scanf(“%d%d%d”,&n,&m,&p);acauto.build_Trie();acauto.build_Fail();acauto.build_Mrx();for(int i=0;i<T;i++)Std.x[i][i]=1;Ini.x[0][0]=1;MRX Temp=power(Trs,n);Temp=Temp*Ini;int ans=0;for(int i=0;i<m;i++)ans=(ans+Temp.x[i][0])%p;printf(“%d\n”,ans);/* MRX ToT=Ini;for(int i=1;i<=n;i++)ToT=Trs*ToT;*/return 0;}
，绚丽的民族风情，悠久的历史文化。抛开尘世的纷扰，
