我又来复习\(kmp\)了

其实这道题主要是一个矩阵乘法，但是\(kmp\)在其中也有着非常重要的作用

我们可以这样定义状态\(dp[i][j]\)表示文本串进行到了\(i\)位置，同时文本串在最后和模式串匹配了一共\(j\)位的方案数

于是答案就是\(\sum_{i=0}^{m-1}dp[n][i]\)

之后我们想一下转移

显然\(dp[i]\)需要从\(i-1\)转移过来

但是怎么转移呢

有一个非常直观也非常\(sb\)的想法就是直接\(dp[i][j]=dp[i-1][j-1]\)

毕竟再补上模式串的第\(j\)位就可以啦

但是转移不止这些

那四个画出来的部分是\(next[j]\)

如果我们在转移\(dp[i][j]\)的状态的时候并不让文本串的第\(i\)位和模式串的第\(j\)位相等，而是在这里填上模式串的\(next[j]\)位置上的数

那么很显然\(dp[i-1][nx[j]]+=dp[i-1][j-1]\)

所以我们用\(kmp\)预处理出来一个这样的数组\(a[i][j]\)表示匹配到在模式串上匹配\(j\)向\(i\)转移的时候可以填几个数字

所以现在就有

\[dp[i][j]=\sum_{k=0}^{m-1}dp[i-1][k]*a[i][k]\]

显然这是一个矩阵乘法就可以优化的柿子

现在的问题就变成了\(a\)数组怎么求

首先求出\(next\)数组，之后枚举这一位填什么，之后往前跳\(nx\)，直到匹配就好了

代码

#include
    
     #include
     
      #include
      
       #define re register#define maxn 21int dp[1001][maxn];char S[maxn];int n,m,mod;int nx[maxn];int ans[maxn][maxn];int a[maxn][maxn];inline void did_a(){    int mid[maxn][maxn];    for(re int i=0;i
       
        =mod) a[i][j]%=mod;            }}inline void did_ans(){    int mid[maxn][maxn];    for(re int i=0;i
        
         =mod) ans[i][j]%=mod;            }}inline void quick(int b){    while(b)    {        if(b&1) did_ans();         b>>=1;         did_a();    }}int main(){    scanf("%d%d%d",&n,&m,&mod);    scanf("%s",S+1);    nx[0]=nx[1]=0;    for(re int i=2;i<=m;i++)    {        int p=nx[i-1];        while(p&&S[p+1]!=S[i]) p=nx[p];        if(S[p+1]==S[i]) nx[i]=++p;            else nx[i]=0;    }    for(re int i=0;i