Time Limit: 1 Sec  Memory Limit: 162 MB

Submit: 2486  Solved: 1524

[][][]

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

 

题解：

　

　首先想暴力的算法，假设构造出一个字符串来和A串进行匹配，f[i][j]代表前i个位置的数中后缀有j位是匹配的，当前要在第i+1个位置新加入一个数字k，看此时对f[i+1][x]的贡献，来更新f[i+1][x]。

①：如果k==A[j+1]，则f[i+1][j+1]+=f[i][j]   

②：如果不相等，让 j 根据对于A串构造出的next[]进行跳转，直到跳转后的j使得A[j+1]==k，即f[i+1][tmp+1]=f[i+1][tmp+1]+f[i][j]

③：如果以上两种情况都不满足的话，就看看k是不是和A[1]相等，如果相等：f[i+1][1]=f[i+1][1]+f[i][j]

④：实在没法匹配，就只能f[i+1][0]=f[i+1][0]+f[i][j]

最后：

for(LL j=0;j<=M-1;j++) ans+=(f[N][j])%mod,ans%=mod; 得出是就是答案。

　　40分暴力：

1 #include
      
        2 using namespace std; 3 typedef long long LL; 4 LL N,M,K; 5 LL f[2000][30],next[30],lenA,A[30],ans,mod; 6 char s[30]; 7 int main(){ 8     scanf("%lld%lld%lld%s",&N,&M,&K,s+1); lenA=strlen(s+1); mod=K; 9     for(LL i=1;i<=lenA;i++) A[i]=s[i]-'0';10     for(LL j=0,i=2;i<=lenA;i++){11         while(A[j+1]!=A[i]&&j) j=next[j];12         if(A[j+1]==A[i]) j++;13         next[i]=j;14     }15     f[1][0]=9; f[1][1]=1;16     for(LL i=1;i<=N-1;i++){
    //前 i个字符 17         for(LL j=0;j<=min(M-1,i);j++){
    //末尾有j位匹配 18             for(LL k=0;k<=9;k++){
    //再加入数字 k 19                 LL tmp=j; bool vis=false;20                 if(A[tmp+1]==k){21                 f[i+1][j+1]=(f[i+1][j+1]+f[i][j]%mod)%mod;22                     vis=true;23                     continue;24                 }25                 else{26                     while(next[tmp]!=0){27                         tmp=next[tmp];28                         if(A[tmp+1]==k){29                             f[i+1][tmp+1]=(f[i+1][tmp+1]+f[i][j]%mod)%mod;30                             vis=true;31                             break;32                         }33                     }34                 }35                 if(vis==false){36                     if(A[1]==k) f[i+1][1]=(f[i+1][1]+f[i][j]%mod)%mod;37                     else f[i+1][0]=(f[i+1][0]+f[i][j]%mod)%mod;38                 }39             }40         }41     }42     for(LL j=0;j<=M-1;j++) 43         ans+=(f[N][j])%mod,ans%=mod;44     printf("%lld",ans);45     return 0;46 }
      

 

1 #include
      
        2 using namespace std; 3 int n,m,mod,ans; 4 char str[25]; 5 int next[25],s[25],a[25][25],c[25][25],f[25],d[25]; 6 int idx(char ch){ 7     return ch-'0'; 8 } 9 void KMP(){10     for(int i=0;i
       
        >str;48     KMP(); Makematrix(); 49     f[0]=1;50     while(n){51         if(n&1) muti1();52         muti2(); n>>=1;53     }54     for(int i=0;i