按照一般思路

设f[i][j]为准考证前i个现在最大匹配到不吉利的数字的前j个的个数

g[j][k]表示不吉利的数字的前j个加一位可以匹配到前k个数字的方法数

(裸的kmp欸)

那么转移可以表示为f[i+1][k]=f[i][j]*g[j][k];

如果单纯转移，则复杂度为10^9*1000（nk）

然后我们考虑用矩阵优化一下

#include
     
      #define re return#define inc(i,l,r) for(int i=l;i<=r;++i)const int maxn=31;using namespace std;int n,m,ans,mod,nt[maxn];char s[maxn],ss[maxn];template
      
       inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}struct Matrix{    int n,g[25][25];    //初始化清0    inline void init()    {        inc(i,0,m)inc(j,0,m)        g[i][j]=0;    }//重载矩阵乘法    inline Matrix operator*(Matrix b)const     {        Matrix c;        c.init();        inc(i,0,m-1)inc(j,0,m-1)        inc(k,0,m-1)        c.g[i][j]=(c.g[i][j]+g[i][k]*b.g[k][j])%mod;        re c;    }    }a;//kmp先行配对g[i][j]inline void KMP(){    nt[1]=0;    inc(i,2,m)    {        int j=nt[i-1];        while(j&&s[j+1]!=s[i])j=nt[j];        if(s[j+1]==s[i])++j;        nt[i]=j;    }}inline void PRE(){    inc(i,0,m-1)    inc(c,'0','9')    {        int j=i;        while(j&&s[j+1]!=c)j=nt[j];        if(s[j+1]==c)++j;        a.g[i][j]=(a.g[i][j]+1)%mod;    }}int main(){    rd(n),rd(m),rd(mod);    scanf("%s",s+1);        Matrix ret,F;    ret.init();    F.init();    a.init();        KMP();    PRE();        //单位矩阵     inc(i,0,m)    ret.g[i][i]=1;    //快速幂    while(n)    {        if(n&1)ret=ret*a;        a=a*a;        n>>=1;     }    //原始状态f[0][0]=1；    F.g[0][0]=1;    F=F*ret;    //根据原始状态推得有答案值仅在F.g[0][x]    inc(i,0,m-1)    ans=(ans+F.g[0][i])%mod;        printf("%d",ans);    re 0;}