大佬讲的真吼->这里
首先考虑dp，设$f[i][j]$表示长串匹配到第$i$位，短串最多匹配到$j$位时的方案数
那么答案就是$sum_{i=0}^{m-1}f[n][i]$
然后考虑一下dp的转移，一种是加进的新字符$i+1$与$j+1$匹配，那么$dp[i][j]$可以直接转移到$dp[i+1][j+1]$
然后如果不匹配怎么办？这种时候，有可能新串的一个后缀和短串的一个前缀有了匹配
对于这一点，我们就是要知道，对于一个匹配到长度为$j$的串，转移到$k$的串的方案，也就对于长度为$i$的串，加一个数字，能加入多少种数字，使得长度为$j$的匹配变成长度为$k$的匹配
然后这个可以用kmp计算
然后看一下dp式子$f[i][j]=sum{k=0}^{m-1}f[i-1][k]*g[k][j]$
那这就是一个矩阵乘法了……因为$g[i][j]$是固定不变的，所以把$f[i][j]$看做一个矩阵
那么$F[i]=F[i-1]*G$
那么矩阵快速幂一下就行了
1 //minamoto 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 using namespace std; 6 const int N=10005; 7 int f[N][30],n,m,mod; 8 int kmp[N],match[N][55];char s[N]; 9 inline void init(){ 10 kmp[0]=-1; 11 for(int i=1;i<=m;++i){ 12 int j=kmp[i-1]; 13 while((~j)&&s[j+1]!=s[i]) j=kmp[j]; 14 kmp[i]=j+1; 15 } 16 kmp[0]=0; 17 for(int i=0;i<m;++i) 18 for(int j='0';j<='9';++j){ 19 int tmp=i; 20 while(s[tmp+1]!=j&&tmp) tmp=kmp[tmp]; 21 if(s[tmp+1]==j) ++tmp; 22 if(tmp<m) ++match[i][tmp]; 23 } 24 } 25 struct Matrix{ 26 int g[25][25]; 27 Matrix(){memset(g,0,sizeof(g));} 28 Matrix operator *(Matrix B){ 29 Matrix res; 30 for(int i=0;i<m;++i) 31 for(int j=0;j<m;++j) 32 for(int k=0;k<m;++k) 33 (res.g[i][j]+=g[i][k]*B.g[k][j])%=mod; 34 return res; 35 } 36 }F,G; 37 inline Matrix ksm(Matrix A,int k){ 38 Matrix res; 39 for(int i=0;i<=m;++i) res.g[i][i]=1; 40 while(k){ 41 if(k&1) res=res*A; 42 A=A*A,k>>=1; 43 } 44 return res; 45 } 46 int main(){ 47 // freopen("testdata.in","r",stdin); 48 scanf("%d%d%d%s",&n,&m,&mod,s+1); 49 init(); 50 F.g[0][0]=1; 51 for(int i=0;i<=m;++i) 52 for(int j=0;j<=m;++j) 53 G.g[i][j]=match[i][j]; 54 G=ksm(G,n); 55 F=F*G; 56 int ans=0; 57 for(int i=0;i<m;++i) (ans+=F.g[0][i])%=mod; 58 printf("%d ",ans); 59 return 0; 60 }