题意&思路
代码
/*
题意简化:
n 位数 X1 X2⋯Xn,m位 A1A2⋯Am有 m位,不出现是指 X1X2⋯Xn中没有恰好一段等于 A1A2⋯Am,A1和 X1 可以为 0,问字符串种数?
解题方法:
算法一:KMP+ 快速幂 +矩阵乘法
*/
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=25;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll qmi(ll m,ll k, ll p=mod){int res=1%p,t=m;while(k){if(k&1)res=res*t%p;t=t*t%p;k>>=1;}return res;}
ll inv(ll a){return qmi(a,mod-2);}
int n,m,mo;
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 k=0;k<m;k++)
for(int j=0;j<m;j++)
t[i][j]=(t[i][j]+(ll)a[i][k]*b[k][j])%mo;
memcpy(c,t,sizeof t);
}
int int_qmi(int k){
int f0[N][N]={1};
while(k){
if(k&1)mul(f0,f0,a);
mul(a,a,a);
k>>=1;
}
int res=0;
for(int i=0;i<m;i++)res=(res+f0[0][i])%mo;
return res;
}
int main(){
cin>>n>>m>>mo;
cin>>str+1;
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(int c='0';c<='9';c++)
{
int k=j;
while(k&&str[k+1]!=c)k=ne[k];
if(str[k+1]==c)k++;
if(k<m)a[j][k]++;
}
cout<<int_qmi(n)<<endl;
return 0;
}