[HNOI2008]GT考试

emm。。。这篇博文，不知道为啥。。。被博客园私吞了。。。我没发出来。。。

今天来补一下。。。QVQ

这个题是一个 KMP+矩阵快速幂 的恶心题目。。。QVQ

写题解也比较麻烦吧。。。

 通过分析题目我们可以发现这个题如果转换为求准考证号有多少段等于不吉利数字。。。

大家肯定都会吧。。。QVQ

轻松加愉快的一个 KMP 写上。。。

接下来我们讨论递推式子怎么写。。。QVQ

我们设一个数组 f [ i , j ]

表示，到了第 i 位，前面有 j 位不吉利数字匹配，有 f [ i , j ] 个方案。。。

以样例为例

假使我们现在查到 f [ i , 2 ]

那么我们接下来就需要讨论了。。。

如果下一位取到 1 那么我们就有 f [ i+1 , 3 ] += f [ i , 2 ]

如果下一位不取 1 那么我们就有 f [ i+1 , 0 ] += f [ i , 2 ]

那么当 j == 3 时这个状态是不合法的。。。那么我们不统计就好了。。。

这时候本蒟蒻想到了个好东西。。。矩阵快速幂。。。

对于每个合法的状态，在矩阵相应的位置++

然鹅，看大佬的博客说这个东西是必须的。。。要不然不过。。。

更具体的请参悟代码。。。QVQ

呆码：

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

int n,m,mo,next[25];
char ch[25];

struct asd{
    int m[25][25];
} a,b;

inline asd mul(asd a,asd b)
{
    asd ans;
    memset(ans.m,0,sizeof(ans.m));
    for(int i=0;i<=m-1;i++)
        for(int j=0;j<=m-1;j++)
        {
            for(int k=0;k<=m-1;k++)
                ans.m[i][j]=(ans.m[i][j]+a.m[i][k]*b.m[k][j])%mo;
        }
    return ans;
}

inline void qmo()
{
    while(n)
    {
        if(n&1)
        {
            a=mul(a,b);
            n--;
        }
        b=mul(b,b);
        n>>=1;
    }
}

int main()
{
    scanf("%d%d%d",&n,&m,&mo);
    scanf("%s",ch+1);
    int k=0;
    for(int i=2;i<=m;i++)
    {
        while(k && ch[k+1]!=ch[i]) k=next[k];
        if(ch[k+1]==ch[i]) k++;
        next[i]=k;
    }
    for(int i=0;i<=m-1;i++)
        for(int j=0;j<=9;j++)
        {
            k=i;
            while(k && ch[k+1]-'0'!=j) k=next[k];
            if(ch[k+1]-'0'==j) k++;
            if(k!=m) b.m[k][i]=(b.m[k][i]+1)%mo;
        }
    for(int i=0;i<=m-1;i++)
        a.m[i][i]=1;
    qmo();
//    for(int i=0;i<m;i++)
//    {
//        for(int j=0;j<m;j++)
//            cout<<b.m[i][j]<<" ";
//        cout<<endl;
//    }
    int ans=0;
    for(int i=0;i<=m-1;i++)
        ans=(ans+a.m[i][0])%mo;
    printf("%d",ans%mo);
}