BZOJ1009-[HNOI2008] GT考试

[BZOJ1009][HNOI2008] GT考试

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

题解

       先想到dp(应该非常明显)。

       f[i , j]表示前 i 个准考证号匹配到不吉利串第 j 个的方案。

       接下来是转移。举个例子，样例，比如当前匹配到了第2位，也就是说前 i 位的结尾是11

       对于第 i+1 个字符，如果是 1 的话，接着匹配到不吉利串第 3 位，不是 1 的话就匹配到第 0 位了

       也就是说前 i 位匹配到了不吉利串 j 位，加入 i+1 这个字符，有不同情况，有一些会转移到j+1，一些会转移到其他的，写成一些形如f[i+1 , k] += f[i , j]的式子……

       f[i+1,3]+=f[i,2]

       f[i+1,0]+=f[i,2]

       暴力显然超时，怎么办？用矩阵！

       你需要把一个答案矩阵f[i , j]转移到f[i+1,j]。

       即枚举i+1可能出现的字符，然后看n个f[i,j]分别转移到哪去，就在转移矩阵的这个转移路径上+1

       按照这个思路用kmp写出转移矩阵。

Code：

#include<bits/stdc++.h>
#define N 105
using namespace std;
char ch[N];
int fail[N],a[N][N],b[N][N],n,m,mod;
void mul(int a[N][N],int b[N][N],int ans[N][N])
{
    int tmp[N][N];
    for(int i=0;i<m;i++)
        for(int j=0;j<m;j++)
        {
            tmp[i][j]=0;
            for(int k=0;k<m;k++)
                tmp[i][j]=(tmp[i][j]+a[i][k]*b[k][j])%mod;
        }
    for(int i=0;i<m;i++)
        for(int j=0;j<m;j++)
            ans[i][j]=tmp[i][j];
}
int main()
{
    int p=0;
    scanf("%d%d%d",&n,&m,&mod);
    scanf("%s",ch+1);
    fail[1]=0;
    for(int i=2;i<=m;i++)
    {
        while(p>0&&ch[i]!=ch[p+1])p=fail[p];
        if(ch[i]==ch[p+1])p++;
        fail[i]=p;
    }
    for(int i=0;i<m;i++)
        for(int j=0;j<=9;j++)
        {
            int p=i;
            while(p>0&&j!=ch[p+1]-'0')p=fail[p];
            if(j==ch[p+1]-'0')p++;
            if(p!=m)b[p][i]=(b[p][i]+1)%mod;
        }
    for(int i=0;i<m;i++)a[i][i]=1;
    while(n)
    {
        if(n&1)mul(a,b,a);
        mul(b,b,b);
        n>>=1;
    }
    int sum=0; 
    for(int i=0;i<m;i++)
        sum=(sum+a[i][0])%mod;
    printf("%d",sum);
    return 0;
}