【bzoj1009】[HNOI2008]GT考试

2015.04.14 20:38 Tue | 18次阅读 | 旧日oi | 固定链接 | 源码

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

题解

从刚学完KMP和矩阵老师就让我有时间做一下这个题,一直拖啊拖,前两天才把它a了
网上的题解好少,难道是我搜索的姿势不对?应该深搜还是宽搜?
综合了好多篇题解,自己又脑补+yy了好久,总算是明白了
设dp[i][j]表示前i位在末尾匹配了j位的方案数,初始状态是dp[0][0]=1;
我们考虑转移,先枚举dp[i][j]中的j,令t=j,枚举第i+1位的取值,看是s[t+1]是否和其匹配,如果不匹配,则跳到失配指针,直到t=0或者匹配成功
若是匹配成功,t++;
找到了这个点意味着什么呢? 就是若第i+1位为所枚举的取值,则dp[i+1][t]可以由dp[i][j]转移过来
于是我们可以如下建立一个矩阵
scanf("%d%d%d",&n,&m,&mod);
scanf("%s",s+1);
get_next();
for(int i=0;i<m;i++)
{
for(int j=0;j<10;j++)
{
int t=i;
while(t&&s[t+1]-'0'!=j) t=next[t];
if(s[t+1]-'0'==j) t++;
f.m[i][t]=(f.m[i][t]+1)%mod;
}
}
注意这里的next数组和平常的不太一样,它求的是若失配,则跳到上一个和它一样的字符的地方,有点像正常的kmp都往前移了一位的感觉……当然正常的也不是不能写
这个矩阵的f.m[i][j]表示的就是匹配到由上一次的匹配到i位到这次的匹配到j位的方案数
矩阵乘法的形式是sigma(a.m[i][k]*b.m[k]j),本题里的意义就是前i位匹配了k位之后,可以转移到前i+1位匹配了j位的方案数,而这里的i+1,又自然的变成了新矩阵的第i行也就是c.m[i][j]=sigma(a.m[i][k]*b.m[k]j),就这样,从第i位到第i+1位的转移就完成了。理解这里我费了好长时间啊。。肯定是我太弱了……
最后的答案就是把这个矩阵f乘n次之后再和初始矩阵,也就是st.m[0][0]=1,相乘,得到的ans矩阵的ans.m[0][0]就是答案,或者不乘初始矩阵,直接求和f.m[0][0~m-1]也可以。
啊,终于写完了,我也算是理解透了,希望能对大家也有一些帮助。

我的程序

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,m,mod;
char s[1005];
int next[1005];
void get_next()
{
    int j=0;
    next[1]=0;
    for(int i=2;i<=m;i++)
    {
        while(j&&s[j+1]!=s[i])
        {
            j=next[j];
        }
        if(s[j+1]==s[i]) j++;
        next[i]=j;
    }
}
struct Matrix{
    int m[25][25];
}f;
Matrix operator * (Matrix a,Matrix b)
{
    Matrix c;
    memset(&c,0,sizeof(c));
    for(int i=0;i<m;i++)
    for(int j=0;j<m;j++)
    for(int k=0;k<m;k++)
    c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%mod;
    return c;
}
Matrix qpow(Matrix a,int k)
{
    Matrix ret;
    memset(&ret,0,sizeof(ret));
    for(int i=0;i<m;i++) ret.m[i][i]=1;
    while(k)
    {
        if(k&1) ret=ret*a;
        k>>=1;
        a=a*a;
    }
    return ret;
}
int main()
{
    scanf("%d%d%d",&n,&m,&mod);
    scanf("%s",s+1);
    get_next();
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<10;j++)
        {
            int t=i;
            while(t&&s[t+1]-'0'!=j) t=next[t];
            if(s[t+1]-'0'==j) t++;
            f.m[i][t]=(f.m[i][t]+1)%mod;
        }
    }
    Matrix a=qpow(f,n);
    int ans=0;
    for(int i=0;i<m;i++)
    ans=(ans+a.m[0][i])%mod;
    printf("%d\n",ans);
    return 0;
}```