传送门
f[i][j]f[i][j]f[i][j]表示从状态“匹配了前i位”转移到“匹配了前j位”的方案数。
这个东西单次是可以通过跳kmp的fail数组得到的。
考虑到每次都是一样的就可以用矩阵快速幂优化一波。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,mod,fail[21];
bool vis[21][10];
char s[21];
struct Matrix{
int val[21][21];
Matrix(int x=0){
memset(val,0,sizeof(val));
for(int i=0;i<m;++i)val[i][i]=x;
}
inline Matrix operator*(const Matrix&b){
Matrix ret(0);
for(int i=0;i<m;++i)for(int k=0;k<m;++k)for(int j=0;j<m;++j)(ret.val[i][j]+=val[i][k]*b.val[k][j]%mod)%=mod;
return ret;
}
friend inline Matrix operator^(Matrix a,int p){Matrix ret(1);for(;p;p>>=1,a=a*a)if(p&1)ret=ret*a;return ret;}
}ans,a;
int main(){
scanf("%d%d%d%s",&n,&m,&mod,s+1);
ans.val[0][0]=1;
for(int i=0;i<m;++i)a.val[i][0]=9;
for(int i=0;i<m-1;++i)a.val[i][i+1]=1;
for(int i=2,j=0;i<=m;++i){
while(s[i]!=s[j+1]&&j)j=fail[j];
if(s[i]==s[j+1])++j;
fail[i]=j;
}
for(int i=1;i<m;++i){
int j=i;
do{
j=fail[j];
if(s[i+1]!=s[j+1]&&!vis[i][s[j+1]-'0']){
vis[i][s[j+1]-'0']=1;
++a.val[i][j+1];
--a.val[i][0];
}
}while(j);
}
ans=ans*(a^n);
int ret=0;
for(int i=0;i<m;++i)(ret+=ans.val[0][i])%=mod;
cout<<ret;
return 0;
}