【KMP】【矩阵加速】【递推】洛谷 P3193 [HNOI2008]GT考试题解

看出来矩阵加速也没看出来KMP……

题目描述

阿申准备报名参加 GT 考试，准考证号为$N$位数$X_1,X_2…X_n(0\le X_i\le9)$，他不希望准考证号上出现不吉利的数字。他的不吉利数学$A_1,A_2…A_m(0\le A_i\le 9)$有$M$位，不出现是指$X_1,X_2…X_n$中没有恰好一段等于$A_1,A_2…A_m$，$A_1$和$X_1$可以为$0$。

输入输出格式

输入格式：

第一行输入$N,M,K$，接下来一行输入$M$位的数。

输出格式：

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

输入输出样例
输入样例#1：
4 3 100

111
输出样例#1：
81
说明

$N\le 10^9,M\le 20,K\le 1000$

题解：

这个题虽然没怎么提字符串，但是KMP却是解题的关键。

首先令f[i][j]表示到第i个为止连续匹配了j个的方案数，考虑DP或递推。

一开始以为所有的转移都不带系数，感觉后面接一个数要么能继续匹配，要么不能继续匹配，只有两种转移情况，然后发现是比较固定的，$N\le 10^9$就可以矩阵加速完成推导了。

不过怎么改都过不了样例。想到后面接的数字有10种情况，只有1种可以连续，就分配1:9的倍数比例转移，当前方案数×9转移到失配，当前方案数×1转移到下一个。这时候样例过了，手敲的几组~~很弱的~~数据也没问题。交上去一分没有……

结果看了一些题解才知道，上面的方案数×9转移到失配中的失配不一定直接到0了，而是可能失配到中间，也就是可以从半路接着匹配到其它的，这里就和KMP不谋而合了。比如

1313匹配到

   ↑

1312

虽然在最后一位失配了，但是不至于全部重来，可以只用移2位，得到

1313

   ↑

1312 后面的让之后的转移去做好了

因此$f[i][j]=\sum\limits_{k=1}^{m-1}f[i-1][k]*a[i][k][j]$，$a[i][k][j]$表示到第i-1个字符连续匹配成功k次转移到第i个字符连续转移j次的方案数。正常情况下$a[i][k][k+1]=1$，然后KMP的nxt数组就派上用场了，它可以求出下一个字符是c时的最长匹配$f[i_1][j_1]$，让方案数变为加上$f[i_1][j_1]$。

初始化$f[0][0]=1$，因为对每一个$i$，$a$数组都是一定的，所以放进矩阵里转移，进行矩阵加速就可以了。状态矩阵是$(m+1)\times 1$的，转移矩阵就需要$(m+1)\times (m+1)$。

就有了$$\begin{bmatrix}
a[0][1] & a[1][1] & \cdots & a[m][1]\\
a[0][2] & a[1][2] & \cdots & a[m][2]\\
\cdots & \cdots & \ddots & \cdots\\
a[m][1] & a[m][2] & \cdots & a[m][m]
\end{bmatrix}
\times \begin{bmatrix}
f[i][0]\\
f[i][1]\\
\cdots \\
f[i][m]
\end{bmatrix}
=\begin{bmatrix}
f[i+1][0]\\
f[i+1][1]\\
\cdots \\
f[i+1][m]
\end{bmatrix}$$

在计算$a$数组时，方法和KMP匹配很像，只不过每次都要匹配'0'~'9'，而且不是真正的KMP，所以变量$j$都要赋成$i-1$。

Code：

#include<cstdio>

#include<cstring>

long long p;

struct matrix//矩阵部分

{

    long long a[25][25];

    int x,y;

    matrix(int x,int y)

    {

        this->x=x;

        this->y=y;

        memset(a,0,sizeof(a));

    }

    matrix()

    {

        memset(a,0,sizeof(a));

    }

    matrix mul(matrix m)

    {

        matrix n(x,m.y);

        for(int i=1;i<=x;++i)

            for(int j=1;j<=m.y;++j)

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

                {

                    n.a[i][j]+=a[i][k]*m.a[k][j]%p;

                    n.a[i][j]%=p;

                }

        return n;

    }

};

int nxt[30],m;

char t[30];

void kmp()

{

    for(int i=2,j=0;i<=m;++i)//单纯求nxt

    {

        while(j&&t[j+1]!=t[i])

            j=nxt[j];

        if(t[j+1]==t[i])

            ++j;

        nxt[i]=j;

    }

}

int main()

{

    int n;

    scanf("%d%d%lld",&n,&m,&p);

    scanf("%s",t+1);

    kmp();

    matrix x(m+1,m+1);

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

        for(int j='0';j<='9';++j)//每个都要匹配，位置不一定都相同

        {

            int k=i-1;

            while(k&&(k==m||t[k+1]!=j))

                k=nxt[k];

            if(t[k+1]==j)

                ++k;

            x.a[k+1][i]++;

        }

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

    {

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

            printf("%d ",x.a[i][j]);

        puts("");

    }

    matrix y(m+1,1);

    y.a[1][1]=1;

    matrix ans(m+1,m+1);

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

        ans.a[i][i]=1;

    while(n)

    {

        if(n&1)

            ans=ans.mul(x);

        x=x.mul(x);

        n>>=1;

    }

    ans=ans.mul(y);

    long long sum=0;

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

        sum+=ans.a[i][1];

    printf("%lld\n",sum%p);

    return 0;

}

巴特西

【KMP】【矩阵加速】【递推】洛谷 P3193 [HNOI2008]GT考试题解

题目描述

输入输出格式

输入输出样例

说明

题解：

Code：

最新文章

热门文章

巴特西

【KMP】【矩阵加速】【递推】洛谷 P3193 [HNOI2008]GT考试 题解

题目描述

输入输出格式

输入输出样例

说明

题解：

Code：

最新文章

热门文章

【KMP】【矩阵加速】【递推】洛谷 P3193 [HNOI2008]GT考试题解