首页 > 代码库 > Bzoj3530 [Sdoi2014]数数

Bzoj3530 [Sdoi2014]数数

 

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 744  Solved: 394

Description

我们称一个正整数N是幸运数,当且仅当它的十进制表示中不包含数字串集合S中任意一个元素作为其子串。例如当S=(22,333,0233)时,233是幸运数,2333、20233、3223不是幸运数。
    给定N和S,计算不大于N的幸运数个数。

Input


    输入的第一行包含整数N。
    接下来一行一个整数M,表示S中元素的数量。
    接下来M行,每行一个数字串,表示S中的一个元素。

Output

    输出一行一个整数,表示答案模109+7的值。

Sample Input

20
3
2
3
14

Sample Output

14

HINT

 

 下表中l表示N的长度,L表示S中所有串长度之和。


1 < =l < =1200 , 1 < =M < =100 ,1 < =L < =1500

 

Source

Round 1 day 1

 

AC自动机上的DP

只比trie树上的dp稍麻烦一点。

先建好trie树,设置好AC自动机,然后跑数位DP。先单独处理数长度小于N长度的情况,此时不需要考虑最高位限制。之后处理数长度等于N长度的情况,此时最高位有没有填满要分开决策。

具体看代码:

  1 /*by SilverN*/  2 #include<iostream>  3 #include<algorithm>  4 #include<cstring>  5 #include<cstdio>  6 #include<cmath>  7 #include<queue>  8 using namespace std;  9 const int mod=1e9+7; 10 int t[1510][11],cnt=1; 11 bool end[1510];int fail[1510]; 12 void init(){for(int i=0;i<=9;i++)t[0][i]=1;} 13 void insert(char s[]){ 14     int rt=1,i,j; 15     int len=strlen(s); 16     for(i=0;i<len;i++){ 17         if(!t[rt][s[i]-0])t[rt][s[i]-0]=++cnt; 18         rt=t[rt][s[i]-0]; 19     } 20     end[rt]=1; 21     return; 22 } 23 int q[15100],hd,tl; 24 void Build(){ 25     hd=0,tl=1; 26     q[++hd]=1; 27     fail[1]=0; 28     while(hd<=tl){ 29         int now=q[hd++]; 30         end[now]|=end[fail[now]]; 31         for(int i=0;i<=9;i++){ 32             int v=t[now][i]; 33             if(!v){ 34                 t[now][i]=t[fail[now]][i]; 35             } 36             else{ 37                 int k=fail[now]; 38                 while(!t[k][i])k=fail[k]; 39                 fail[v]=t[k][i]; 40                 q[++tl]=v; 41             } 42         } 43     } 44     return; 45 } 46 int n,m; 47 char s[1510],c[1510]; 48 int a[1510]; 49 int f[1510][1510][2]; 50 int ans=0; 51 int main(){ 52     scanf("%s",s+1); 53     int i,j; 54     int len=strlen(s+1); 55     for(i=1;i<=len;i++)a[i]=s[i]-0; 56     init(); 57     scanf("%d",&m); 58     for(i=1;i<=m;i++){ 59         scanf("%s",c); 60         insert(c); 61     } 62     Build(); 63     for(i=1;i<=9;i++)//首位  64         if(!end[t[1][i]]) 65             f[1][t[1][i]][0]++; 66     for(i=1;i<len-1;i++)  67         for(j=1;j<=cnt;j++) 68             for(int k=0;k<=9;k++){ 69                 if(!end[t[j][k]]){ 70                     f[i+1][t[j][k]][0]+=f[i][j][0]; 71                     f[i+1][t[j][k]][0]%=mod; 72                 } 73             } 74     for(i=1;i<len;i++) 75      for(j=1;j<=cnt;j++)ans=(ans+f[i][j][0])%mod; 76     memset(f,0,sizeof f); 77     for(i=1;i<=a[1];i++) 78         if(!end[t[1][i]]){ 79             if(i==a[1])f[1][t[1][i]][1]++; 80             else f[1][t[1][i]][0]++; 81         } 82     for(i=1;i<len;i++) 83       for(j=1;j<=cnt;j++) 84         for(int k=0;k<=9;k++) 85             if(!end[t[j][k]]){ 86                 f[i+1][t[j][k]][0]+=f[i][j][0]; 87                 f[i+1][t[j][k]][0]%=mod; 88                 if(k<a[i+1]){ 89                     f[i+1][t[j][k]][0]+=f[i][j][1]; 90                     f[i+1][t[j][k]][0]%=mod; 91                 } 92                 else if(k==a[i+1]){ 93                     f[i+1][t[j][k]][1]+=f[i][j][1]; 94                     f[i+1][t[j][k]][1]%=mod; 95                 } 96             } 97     for(i=1;i<=cnt;i++){ 98         ans=(ans+f[len][i][0])%mod; 99         ans=(ans+f[len][i][1])%mod;100     }101     printf("%d\n",ans);102     return 0;103 }

 

 

Bzoj3530 [Sdoi2014]数数