题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1009
首先想到 确保模式串不出现 就是 确保每个位置的后缀不是该模式串。
为了dp，需要记录第 i 个位置的后缀已经有几位和模式串的前几位吻合了。
所以想到可以转移到 j+1 或 0 。
但其实不一定是0，因为可能和前面的接上。这里就要用kmp了！
注意可以和很多位置接上的时候，应该和最长的那个接上，而不是和每个 nxt 都接上，也不是什么能选择的。
知道了当前 j 能转移到哪些 j ，就可以矩阵优化了。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=;
int n,m,mod,nxt[N],prn,ch[N];
struct Matrix{
int a[N][N];
Matrix(){memset(a,,sizeof a);}
Matrix operator * (const Matrix &b)const
{
Matrix c;
for(int i=;i<m;i++)//<m is enough
for(int k=;k<m;k++)
for(int j=;j<m;j++)
(c.a[i][j]+=a[i][k]*b.a[k][j]%mod)%=mod;
return c;
}
}r,ans;
void getnxt()
{
for(int i=;i<=m;i++)//i=2,or nxt[1]=1
{
int k;
for(k=nxt[i-];ch[k+]!=ch[i]&&k;k=nxt[k]);
nxt[i]=k+(ch[k+]==ch[i]);
}
for(int i=;i<m;i++)//i=0 //<m is enough
{
for(int j=;j<=;j++)
{
int k;
for(k=i;k&&ch[k+]!=j;k=nxt[k]);//k=i!!
if(ch[k+]==j)r.a[i][k+]++;//only keep 1,keep the longest
else r.a[i][]++;
// if(ch[k+1]==j)r.a[i][k+1]++;
// if(ch[1]==j)r.a[i][1]++;// when k=0
// else r.a[i][0]++;//
}
// if(i&&i!=m)r.a[i][i+1]++;//don't forget, and i!=0
}
}
int main()
{
scanf("%d%d%d",&n,&m,&mod);
for(int i=;i<=m;i++)scanf("%1d",&ch[i]);
getnxt();
// for(int i=0;i<m;i++)ans.a[i][i]=1;//!!
ans.a[][]=;
while(n){if(n&)ans=ans*r;r=r*r;n>>=;}
for(int i=;i<m;i++)(prn+=ans.a[][i])%=mod;
printf("%d\n",prn);
return ;
}