字符串dp+矩阵快速幂
[HNOI2008]GT考试
https://ac.nowcoder.com/acm/problem/20064
#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;
} 
投递三维家等公司10个岗位