bzoj 1009 [HNOI2008]GT考试——kmp+矩阵优化dp

题目：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 ;

}