BZOJ-1009: [HNOI2008]GT考试

Description

阿申准备报名参加GT考试，准考证号为N位数X1X2....Xn(0<=Xi<=9),他不希望准考证号上出现不吉利的数字。他的不吉利数学A1A2...Am(0<=Ai<=9)有M位，不出现是指X1X2...Xn中没有恰好一段等于A1A2...Am. A1和X1可以为0 阿申想知道不出现不吉利数字的号码有多少种，输出模K取余的结果.N<=10^9,M<=20,K<=1000

对于不吉利数字建trie图，矩阵乘法优化DP即可。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,m,p,f[30][12],fail[30];
char a[30];
struct matrix1
{
    int a[30][30];
    matrix1(){memset(a,0,sizeof a);}
    matrix1 operator *(const matrix1 z)
    {
        matrix1 ret;
        for(int i=0;i<m;++i)
            for(int j=0;j<m;++j)
                for(int k=0;k<m;++k)
                    ret.a[i][j]+=a[i][k]*z.a[k][j];
        for(int i=0;i<m;++i) for(int j=0;j<m;++j) ret.a[i][j]%=p;
        return ret;
    }
};
struct matrix2
{
    int a[30];
    matrix2(){memset(a,0,sizeof a);}
    matrix2 operator * (const matrix1 z)
    {
        matrix2 ret;
        for(int i=0;i<m;++i)
            for(int j=0;j<m;++j)
                ret.a[i]+=a[j]*z.a[j][i];
        for(int i=0;i<m;++i) ret.a[i]%=p;
        return ret;
    }
};
int main()
{
    scanf("%d%d%d",&n,&m,&p);
    scanf("%s",a+1);
    fail[1]=0;
    for(int i=0;i<10;++i)
    {
        if(a[1]=='0'+i) f[0][i]=1;
        else f[0][i]=0;
    }
    for(int i=1;i<=m;++i)
    {
        for(int j=0;j<10;++j)
        {
            if(a[i+1]=='0'+j) f[i][j]=i+1,fail[i+1]=f[fail[i]][j];
            else f[i][j]=f[fail[i]][j];
        }
    }
    matrix1 x;
    for(int i=0;i<m;++i)
    {
        for(int j=0;j<10;++j)
            x.a[i][f[i][j]]++;
    }
    /*for(int i=0;i<m;++i)
    {
        for(int j=0;j<m;++j)
            printf("%d ",x.a[i][j]);
        puts("");
    }*/
    matrix2 ans; ans.a[0]=1;
    while(n)
    {
        if(n&1) ans=ans*x;
        x=x*x; n>>=1;
    }
    int fna=0;
    for(int i=0;i<m;++i)
        fna=(fna+ans.a[i])%p;
    printf("%d",fna);
    return 0;
}