C++11(clang++ 3.9) 解法, 执行用时: 5ms, 内存消耗: 376K, 提交时间: 2020-07-19 16:48:07

#include <cstring>
#include <iostream>

using namespace std;
const int N=25;

int n, m, mod;
char p[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, 0x00, 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])%mod;
    memcpy(c, t, sizeof t);
}

int qmi(int k){
    int f[N][N]={1};
    while(k){
        if(k&0x01) mul(f, f, a);
        mul(a, a, a);
        k>>=1;
    }
    int ans=0;
    for(int i=0; i<m; ++i) ans=(ans+f[0][i])%mod;
    return ans;
}

int main(){
    cin>>n>>m>>mod;
    cin>>p;
    
    // kmp
    for(int i=1, j=0; i<m; ++i){
        while(j && p[i]!=p[j]) j=ne[j-1];
        if(p[i]==p[j]) ++j;
        ne[i]=j;
    }
    
    // 初始化a[i][j]
    for(int j=0; j<m; ++j){
        for(int c='0'; c<='9'; ++c){
            int k=j;
            while(k && p[k]!=c) k=ne[k-1];
            if(p[k]==c) ++k;
            if(k<m) a[j][k]++;
        }
    }
    
    cout<<qmi(n)<<endl;
    return 0;
}