BZOJ 1009: [HNOI2008]GT考试

阿申准备报名参加 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 位的数。 N<=10^9,M<=20,K<=1000

Output

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

Sample Input

4 3 100
111

Sample Output

81

Solution

我们把不吉利的数字用 s 表示，用 $f_{i,j}$ 表示 $n_i$ 匹配到 $s_j$ 的情况数，则可以用一个转移矩阵 $a$ 通过 $f_{i-1,j}$ 求出 $f_{i,j}$。

$a_{i,j}$ 表示在 $s$ 中匹配了 $i$ 位时，在后面添数，有多少种情况匹配到 $j$ 位，也就是指 $s$ 的前 $i$ 位后面添数后最长的公共前后缀长度为 $j$ 的情况数。

kmp 预处理，然后对于每个 $i$，枚举添加的数，再仿照 kmp 进行处理，即可求出转移矩阵。 矩阵快速幂优化就可以过了，时间复杂度 $O(\log N\cdot M^3)$。

Code

#include<cstdio>

struct _matrix
{
    int s[21][21],a,b;
    _matrix()
    {
        for(int i=0;i<21;i++)
            for(int j=0;j<21;j++)
                s[i][j]=0;
    }
}temp;

int mod;

void mul(_matrix &x,_matrix y)
{
    for(int i=0;i<x.a;i++)
        for(int j=0;j<y.b;j++)
        {
            temp.s[i][j]=0;
            for(int k=0;k<x.b;k++)
                temp.s[i][j]+=x.s[i][k]*y.s[k][j];
            temp.s[i][j]%=mod;
        }
    temp.a=x.a;
    temp.b=y.b;
    x=temp;
}

int m[21],n,f[21];

int main()
{
    int mm;
    scanf("%d%d%d",&n,&mm,&mod);
    char t[20];
    scanf("%s",t);
    for(int i=0;i<mm;i++)m[i+1]=t[i]-48;
    f[1]=0;
    for(int i=2;i<=mm;i++)
    {
        int t=i-1;
        while(t!=0&&m[f[t]+1]!=m[i])t=f[t];
        if(t==0)
        {
            if(m[1]==m[i])
                f[i]=1;
            else
                f[i]=0;
        }
        else
        {
            f[i]=f[t]+1;
        }
    }
    _matrix a;
    a.a=mm+1;
    a.b=mm+1;
    a.s[0][0]=9,a.s[0][1]=1;
    for(int i=1;i<mm;i++)
    {
        for(int j=0;j<10;j++)
        {
            if(m[i+1]==j)
            {
                a.s[i][i+1]++;
                continue;
            }
            int t=i;
            while(t!=0&&m[f[t]+1]!=j)t=f[t];
            if(t==0)
            {
                if(m[1]==j)
                    a.s[i][t+1]++;
                else
                    a.s[i][0]++;
            }
            else
                a.s[i][f[t]+1]++;
        }
    }
    _matrix b;
    b.a=1;
    b.b=mm+1;
    b.s[0][0]=9;
    b.s[0][1]=1;
    int ans=0,to=n-1,no=1;
    while(no<to)
    {
        if(to&no)mul(b,a);
        mul(a,a);
        no<<=1;
    }
    for(int i=0;i<mm;i++)ans+=b.s[0][i];
    printf("%d\n",ans%mod);
    return 0;
}

日期： 2016-09-09

标签： kmp 矩阵快速幂 BZOJ DP

这是一篇旧文，原始文章及评论可在 https://oldblog.mcfx.us/archives/21/ 查看。