BZOJ1009 [HNOI2008]GT考试 矩阵

时间：2021-02-17 05:17:38

去博客园看该题解

题目

【bzoj1009】[HNOI2008]GT考试

Description

阿申准备报名参加GT考试，准考证号为N位数X1X2….Xn(0<=Xi<=9),他不希望准考证号上出现不吉利的数字。他的不吉利数学A1A2…Am(0<=Ai<=9)有M位，不出现是指X1X2…Xn中没有恰好一段等于A1A2…Am. A1和X1可以为0

Input

第一行输入N,M,K.接下来一行输入M位的数。 100%数据N<=10^9,M<=20,K<=1000 40%数据N<=1000 10%数据N<=6

Output

阿申想知道不出现不吉利数字的号码有多少种，输出模K取余的结果.

Sample Input

4 3 100
111

Sample Output

81

题解

　　设dp[i][j]表示总共到做第i位，匹配到第j位的ans，那么对于dp[i][j]到dp[i+1][j'],一定是有固定的转移试的，不会因为运算的值改变而改变。那么想到了什么？矩阵乘法！！设p[i][j]表示匹配到第i位之后，再匹配j，所能得到的新的匹配长度，则可以构建矩阵：对于每一个p[i][j],矩阵的第p[i][j]行第i列加1。

　　至于匹配p[i][j]，两种方法-->暴力匹配或者kmp都可以。

　　矩阵匹配长度范围是：0~m-1。注意，匹配不可到达m，因为如果匹配到了m，那么就是一个不吉利的串出现了！所以只能匹配到第m-1个。那么在kmp的时候，对于匹配0个的转移要特殊处理。

还是举一个例子吧——

　　对于111的转移：

　　要转移到匹配0位，那么如果之前匹配了0或者1或者2位，只要再接下去一个非1的数字即可转移到，那么：

　　dp[i+1][0]= 9* dp[i][0] + 9* dp[i][1] + 9* dp[i][2]

　　同理：

　　dp[i+1][1]= 1* dp[i][0] + 0* dp[i][1] + 0* dp[i][2]

　　dp[i+1][2]= 0* dp[i][0] + 1* dp[i][1] + 0* dp[i][2]

　　再来一个稍微复杂一些的：1213

　　　　　　dp[i][0] dp[i][1] dp[i][2] dp[i][3]

dp[i+1][0]=　 9* 　　8* 　　9* 　　9*

dp[i+1][1]= 　1* 　　1* 　　0* 　　1*

dp[i+1][2]= 　0* 　　1*　　 0* 　　0*

dp[i+1][3]= 　0* 　　0* 　　1* 　　0*

所以，根据dp方程就可以构建矩阵了，然后跑矩阵快速幂，就可以拿到满分了！

代码

#include <cstring>

#include <algorithm>

#include <cstdlib>

#include <cstdio>

#include <cmath>

using namespace std;

const int M=+;

int n,m,mod;

struct Mat{

    int v[M][M];

    void set(int x){

        memset(v,,sizeof v);

        if (x==)

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

                v[i][i]=;

    }

    Mat operator * (Mat x){

        Mat ans;

        ans.set();

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

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

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

                    ans.v[i][j]+=v[i][k]*x.v[k][j];

                    if (ans.v[i][j]>=mod)

                        ans.v[i][j]%=mod;

                }

        return ans;

    }

}M1,My,Mans;

Mat Pow(int y){

    if (y==)

        return M1;

    Mat x=Pow(y/);

    x=x*x;

    if (y&)

        x=x*My;

    return x;

}

int p[M][],next[M];

char ch[M];

int main(){

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

    int k=;

    memset(next,,sizeof next);

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

        while (k>&&ch[i]!=ch[k])

            k=next[k-];

        if (ch[i]==ch[k])

            k++;

        next[i]=k;

    }

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

        if (ch[]==j+'')

            p[][j]=;

        else

            p[][j]=;

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

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

            char chj=j+'';

            int k=i;

            while (k>&&ch[k]!=chj)

                k=next[k-];

            if (ch[k]==chj)

                k++;

            p[i][j]=k;

        }

    M1.set();

    My.set();

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

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

            My.v[i][p[i][j]]++;

    Mans=Pow(n);

    int ans=;

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

        ans=(ans+Mans.v[][i])%mod;

    printf("%d",ans);

    return ;

}

相关文章