1009: [HNOI2008]GT考试

1009: [HNOI2008]GT考试

Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 5006 Solved: 3150
[Submit][Status][Discuss]

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

HINT

Source

[Submit][Status][Discuss]

---

dp思路：处理到每一位时维护前(forall iin[0,m])A的前i项重叠的情况数，dp即可
kmp处理出不吉利数字的前缀，并建出矩阵。
快速米求解即可

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define max(a,b) ((a)>(b) ? (a): (b))
#define min(a,b) ((a)<(b) ? (a): (b))
#define LL long long
using namespace std;

int i,m,n,j,k,a[100001],ans,nex[100001];

struct vv
{
    int g[30][30];
} f,d,e;

void cs(vv &a)
{
    memset(a.g,0,sizeof(a.g));
    for(int i=0;i<m;i++) 
        a.g[i][i]=1;
}

vv cheng(vv a,vv b,int n,int m,int z)
{
    vv o;
    memset(o.g,0,sizeof(o.g));
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            for(int l=0;l<z;l++) 
                o.g[i][j]=(o.g[i][j]%k+a.g[i][l]*b.g[l][j]%k)%k;
        
    return o;
}

vv ksm(int x)
{
    vv w;
    cs(w);
    for(;x>1;x>>=1)
    {
        if(x&1) w=cheng(w,f,m,m,m);
        f=cheng(f,f,m,m,m);
    }
    return cheng(f,w,m,m,m);
}

void kmp()
{
    int j=0;
    nex[1]=0;
    for(int i=2;i<=m;i++)
    {
        while((j>0)&&(a[i]!=a[j+1])) j=nex[j];
        if(a[i]==a[j+1]) j++;
        nex[i]=j;
    }
}

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(i=1;i<=m;i++) scanf("%1ld",&a[i]);
    kmp();
    
    for(i=1;i<m;i++)
    {
        int j=i, l=0;
        bool bb[11];
        memset(bb,0,sizeof(bb));
        if(i==m-1) bb[a[m]]=1,l=1;
        while(j)
        {
            if(!bb[a[j+1]])	f.g[i][j+1]=1,l+=1;
            bb[a[j+1]]=1;
        
            j=nex[j];
        }
        if(!bb[a[1]]) f.g[i][1]=1, l+=1;
        f.g[i][0]=10-l;
    }
    f.g[0][1]=1;
    f.g[0][0]=9; 
    d.g[0][0]=1;
    vv t=cheng(d,ksm(n),1,m,m);
    for(i=0;i<m;i++)
    ans=(ans+t.g[0][i])%k;
    printf("%d",ans);
}