这个题你发现打暴力的话可以记忆化搜素加剪枝,那么意味着可以递推,我们搜的话就是1010^9我们就往下匹配遇到匹配成功就return,那么我们可以想一下什么决定了状态,我们考虑kmp的过程,对于我们目前匹配到的距离,下一次在匹配时不会用他之后的字符,那么只要我们知道匹配到的距离和已匹配长度就行了,那么我们考虑状态的转移,我们由于要像kmp那样匹配于是我们只要知道在匹配到k位时往下走一个数时匹配到哪,算出a[k][j](在k时到j的方案数),那么新的f[i][j]=∑f[i-1][k]*a[k][j],这里用到了对口遗传的思想,对于舍去的状态,我们不继承就是舍去了
至于钜乘(:••)去某位大佬博客
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,m,k;
char s[];
int next[];
int a[][],b[][],temp[][];
inline void kmp()
{
a[m-][m-]+=;
a[m-][m-]+=;
for(int i=,K=;i<m;i++)
{
while(K&&s[K]!=s[i])
K=next[K-];
if(s[K]==s[i])
K++;
next[i]=K;
for(int j=;j<=;j++)
{
if(j+==s[i])
{
a[m-i-][m-i]+=;
continue;
}
int l=next[i-];
while(l&&s[l]!=j+)
l=next[l-];
if(s[l]==j+)
l++;
a[m-l][m-i]+=;
}
}
}
inline void Init()
{
scanf("%d%d%d%s",&n,&m,&k,s);
kmp();
}
inline void multi(int x[][],int y[][],int len)
{
memset(temp,,sizeof(temp));
for(int i=;i<=m;i++)
for(int j=;j<=len;j++)
for(int l=;l<=m;l++)
temp[i][j]=(temp[i][j]+y[i][l]*x[l][j])%k;
for(int i=;i<=m;i++)
for(int j=;j<=len;j++)
x[i][j]=temp[i][j];
}
inline void work()
{
b[m][]=;
while(n)
{
if(n&)multi(b,a,);
n>>=;
multi(a,a,m);
}
}
inline void print()
{
int ans=;
for(int i=;i<=m;i++)
ans+=b[i][];
ans%=k;
printf("%d",ans);
}
int main()
{
Init();
work();
print();
return ;
}