bzoj1009: [HNOI2008]GT考试（kmp+矩阵乘法）

时间：2021-06-22 05:17:28

1009: [HNOI2008]GT考试

题目：传送门

题解：

　　 看这第一眼是不是瞬间想起组合数学？？？

　　 没错...这样想你就GG了！

　　 其实这是一道稍有隐藏的矩阵乘法，好题！

　　 首先我们可以简化一下题意：给出一个串，要求这个串不包含另一个串的方案个数

　　 这不是kmp吗？！（直接暴力肯定炸）

　　 我们可以再往DP的方面想

　　 f[i][j]表示长度为i的母串的后缀与子串匹配j个长度的方案数

　　 那么ans=Sigma(f[n][0]~f[n][m-1])

　　 那么我们再定义一个c[i][j]表示在子串长度为i的前缀后面加上一个数，令该前缀加上这个数所组成的新字符串与给出子串从头开始所能匹配的长度为j的方案数

　　 那么f[i+1][k]=f[i][j]*c[j][k]

　　 但是还是会炸啊！！！！！！！

　　 这时候怎么就想不到矩乘加速呢？！

　　 c数组不变，而且每次f都要乘一次，很明显可以用矩阵乘法。。。

　　 所以用kmp预处理矩阵就ok，但是c[i][m]不能继承，所以只能从w[i][0]继承，矩乘时就枚举0~m-1

代码：

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 struct matrix

 {

     int m[][];

     matrix(){memset(m,,sizeof(m));}

 }ans;

 char st[];

 int p[];

 int n,m,mod;

 matrix multi(matrix a,matrix b,int n,int m,int p)//[n,m]*[m,p];

 {

     matrix c;

     for(int i=;i<n;i++)

         for(int j=;j<p;j++)

             for(int k=;k<m;k++)

                 c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%mod;

     return c;

 }

 matrix p_m(matrix a,int b)

 {

     matrix sum;

     for(int i=;i<m;i++)sum.m[i][i]=;

     while(b)

     {

         if(b%==)sum=multi(sum,a,m,m,m);

         a=multi(a,a,m,m,m);b/=;

     }

     return sum;

 }

 void kmp()

 {

     p[]=;int j;

     for(int i=;i<=m;i++)

     {

         j=p[i-];

         while(j && st[i]!=st[j+])j=p[j];

         if(st[i]==st[j+])j++;

         p[i]=j;

     }

     for(int i=;i<m;i++)

     {

         for(int y=;y<=;y++)

         {

             j=i;

             while(j && st[j+]-''!=y)j=p[j];

             if(st[j+]-''==y)j++;

             ans.m[j][i]=(ans.m[j][i]+)%mod;

         }

     }

 }

 int main()

 {

     scanf("%d%d%d",&n,&m,&mod);

     scanf("%s",st+);

     kmp();

     ans=p_m(ans,n);

     int sum=;

     for(int i=;i<m;i++)sum=(sum+ans.m[i][])%mod;

     printf("%d\n",sum%mod);

     return ;

 }

相关文章