Cptraser/ 十月 29, 2018/ 2018.10/ 0 comments

[HNOI2008]GT考试

神奇的KMP矩乘,从普及组A到提高组…

题面传送门

我们f(i,j)表示长串匹配到i,短串匹配到j的吉利的方案数。
g(i,j)表示i->j失配的方案数。
考虑转移:

f(i+1,k)+=f(i,j)*g(j,k)k表示失配后短串匹配到哪个位置。

?好像我们会KMP!!!
可以先构造g,原式写为:

f(i,j)=\sum_0^{m-1}f(i-1,k)*g(k,j)

可以看成矩乘:

    \[F(i)=F(i-1)*G\]

然后上快速幂。

#include <cstdio>
#include <string>
#include <iostream>
using namespace std;

int N,M,K,Fail[25],G[25][25],Res[65][65],D[65][65],j,Ans;
char S[25];

void Mul1(void){
    for(int i=0;i<M;i++)
        for(int j=0;j<M;j++)D[i][j]=0;
    for(int i=0;i<M;i++)
        for(int j=0;j<M;j++){
            for(int k=0;k<M;k++)
                D[i][j]+=G[i][k]*G[k][j];
            D[i][j]%=K;
        }
    for(int i=0;i<M;i++)
        for(int j=0;j<M;j++)G[i][j]=D[i][j];
}

void Mul2(void){
    for(int i=0;i<M;i++)
        for(int j=0;j<M;j++)D[i][j]=0;
    for(int i=0;i<M;i++)
        for(int j=0;j<M;j++){
            for(int k=0;k<M;k++)   
                D[i][j]+=G[i][k]*Res[k][j];
            D[i][j]%=K;
        }
    for(int i=0;i<M;i++)
        for(int j=0;j<M;j++)Res[i][j]=D[i][j];     
}


int main()
{
    scanf("%d%d%d%s",&N,&M,&K,S+1);
    for(int i=2;i<=M;i++){
        for(;j&&S[i]^S[j+1];)
            j=Fail[j];
        if(S[j+1]==S[i])j++;
        Fail[i]=j;
    }
    for(int i=0;i<M;i++){
        for(int p='0';p<='9';p++){
            int j=i;
            for(;j&&p^S[j+1];)j=Fail[j];
            if(S[j+1]==p)j++;
            G[i][j]++;
        }
    }
    for(int i=0;i<M;i++)Res[i][i]=1;
    for(;N;N>>=1,Mul1())if(N&1)Mul2();
    for(int i=0;i<M;i++)(Ans+=Res[0][i])%=K;
    cout<<Ans;
}
Share this Post

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*