bzoj1009 / P3193 [HNOI2008]GT考试

P3193 [HNOI2008]GT考试

设$f[i][j]$表示主串匹配到第$i$个位置，不吉利数字匹配到第$j$个位置

$g[i][j]$表示加上某数字使子串原来最多能匹配到第$i$个数字，现在只能匹配到第$j$个数字的方案

那么可以列出方程

$f[i][j]=\sum_{k=0}^{m-1}f[i-1][k]*g[k][j]$

而后面的方案数暴力枚举似乎不行

仔细观察发现介个可以用kmp搞鸭

但是$n<=1e9$，$O(n)$也不行

再仔细观察发现这个式子可以用矩乘搞鸭

蓝后就结束了。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #define re register

 using namespace std;

 char q[];

 int n,m,k,f[],ans;

 struct matrix{

     int a[][];

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

     matrix operator * (const matrix &tmp) const{

         matrix c;

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

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

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

                     c.a[i][j]=(c.a[i][j]+a[i][u]*tmp.a[u][j]%k)%k;

         return c;

     }

     matrix Pow(matrix x,int y){

         matrix res;

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

         for(;y;y>>=,x=x*x)

             if(y&) res=res*x;

         return res;

     }

 }st,g;

 void kmp(){//kmp处理方案数

     int len=strlen(q);

     for(int i=,j;i<len;++i){

         for(j=f[i];j&&q[i]!=q[j];j=f[j]);

         f[i+]= q[i]==q[j] ? j+:;

     }

     for(int i=,j;i<len;++i)

         for(char u='';u<='';++u){

             for(j=i;j&&q[j]!=u;j=f[j]);

             if(q[j]==u) ++j;

             if(j<m) ++g.a[i][j];

         }

 }

 int main(){

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

     scanf("%s",q); kmp();

     st.a[][]=; g=g.Pow(g,n);

     st=st*g;

     for(int i=;i<m;++i) ans=(ans+g.a[][i])%k;

     printf("%d",ans);

     return ;

 }