kmp和矩阵乘法的运用，还是挺明显的
#include<cstdio> #include<cctype> using namespace std; inline void read(int &x){ char ch=getchar();x=0; for(;!isdigit(ch);ch=getchar()); for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+ch-'0'; } char ch[22]; int fl,n,m,mo,f[22],c[22][22],nex[22],a[22][22]; inline int query(int x,int y){return x==y?9:8;} inline void init(){ f[0]=1; for(int i=1;i<=m;i++)ch[i]-='0'; for(int t,i=2;i<=m;i++){ for(t=nex[i-1];ch[t+1]!=ch[i] && t;t=nex[t]); if(ch[t+1]==ch[i])t++; nex[i]=t; } for(int len,i=0;i<m;i++)for(int j=0;j<=9;j++){ if(j==ch[i+1])len=i+1;else{ for(len=nex[i];len && ch[len+1]!=j;len=nex[len]); if(ch[len+1]==j)len++; } if(len==m)continue; c[i][len]++; } } inline void mul(){ for(int i=0;i<m;i++)a[0][i]=0; for(int j=0;j<m;j++) for(int k=0;k<m;k++) (a[0][j]+=f[k]*c[k][j])%=mo; for(int i=0;i<=m;i++)f[i]=a[0][i]; } inline void sqrmul(){ for(int i=0;i<=m;i++)for(int j=0;j<=m;j++)a[i][j]=0; for(int i=0;i<=m;i++) for(int j=0;j<=m;j++) for(int k=0;k<=m;k++) (a[i][j]+=c[i][k]*c[k][j])%=mo; for(int i=0;i<=m;i++)for(int j=0;j<=m;j++)c[i][j]=a[i][j]; } int main(){ read(n),read(m),read(mo);scanf("%s",ch+1); init(); for(;n;n>>=1,sqrmul())if(n&1)mul(); int ans=0; for(int i=0;i<m;i++)ans=(ans+f[i])%mo; printf("%d\n",ans); return 0; }转载于:https://www.cnblogs.com/MikuKnight/p/9782089.html
相关资源：JAVA上百实例源码以及开源项目