mcfx's blog

mcfx's blog - kmp 2016-09-09T20:13:00+08:00 Typecho /feed/atom/category/kmp/ <![CDATA[BZOJ 1009: [HNOI2008]GT考试]]> /archives/21/ 2016-09-09T20:13:00+08:00 2016-09-09T20:13:00+08:00 admin

###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位的数。 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(logN*M^3)$$

###Code
```c++
#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;
}
```

]]>