$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路：

1. 看 f[i][j] 可以转移到哪些 f[i + 1][k]，如果可以转移则 a[j][k] ++，即f[i + 1][k] += f[i][j]
2. 令 F(i) =[f(i, 0), f(i, 1), ..., f(m - 1, 0)]，则 F(i + 1) = F(i) * A
3. 因此，F(n) = F(0) * A^n

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 25;

int n,m,K;
char str[N];
int ne[N];
int a[N][N];

void mul(int c[][N],int a[][N],int b[][N])
{
    static int t[N][N];

    memset(t,0,sizeof t);

    for(int i=0;i<m;i++)
        for(int j=0;j<m;j++)
            for(int k=0;k<m;k++)
                t[i][j]=(t[i][j]+a[i][k]*b[k][j])%K;

    memcpy(c,t,sizeof t);
}

int qmi(int b)
{
    int f[N][N]={1};
    while(b)
    {
        if(b&1) mul(f,f,a); //f = f * a
        mul(a,a,a); //a = a * a
        b>>=1;
    }

    int res=0;
    for(int i=0;i<m;i++) res=(res+f[0][i])%K;

    return res;
}

int main()
{
    cin>>n>>m>>K>>str+1;

    //求 ne 数组
    for(int i=2,j=0;i<=m;i++)
    {
        while(j&&str[j+1]!=str[i]) j=ne[j];
        if(str[j+1]==str[i]) j++;
        ne[i]=j;
    }

    //字符串匹配
    for(int j=0;j<m;j++)
        for(char c='0';c<='9';c++)
        {
            int k=j;
            while(k&&c!=str[k+1]) k=ne[k];
            if(c==str[k+1]) k++;
            if(k<m) a[j][k]++;
        }

    //F[n] = F[0] * A^n
    cout<<qmi(n)<<endl;

    return 0;
}