【HDU3530】 [Sdoi2014]数数（AC自动机+数位DP）

3530: [Sdoi2014]数数
Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 682  Solved: 364
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

【分析】

　　这题AC自动机+数位DP。
　　话说数位DP搞了我好久。主要是联系上AC自动机判病毒串的时候有点卡- -（脑子一片混乱
　　dp方程：f[i][j]表示现在在点j，继续走i步（不经病毒点）的方案数。
　　先把长度小于n的加入ans，我是for了一遍长度累加的（前缀0那里有点坑，so...）
　　然后手动填与n长度相等的串，for一下，判断一下，累加一下，就好了。。你懂的...

　　主要部分：

手动填数部分：

　　注意是不大于N。

完整代码如下：

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<algorithm>
  6 #include<queue>
  7 using namespace std;
  8 #define Maxn 1600
  9 #define Maxl 1600
 10 #define Mod 1000000007
 11 
 12 struct node
 13 {
 14     int fail,mark;
 15     int son[30];
 16 }t[Maxn];int tot;
 17 
 18 int m,sl;
 19 
 20 void upd(int x)
 21 {
 22     t[x].mark=0;
 23     memset(t[x].son,0,sizeof(t[x].son));
 24 }
 25 
 26 char s[Maxl];
 27 char ss[Maxn];
 28 void read_trie()
 29 {
 30     scanf("%s",s+1);
 31     int len=strlen(s+1);
 32     int now=0;
 33     for(int i=1;i<=len;i++)
 34     {
 35         int ind=s[i]-'0'+1;
 36         if(!t[now].son[ind]) 
 37         {
 38             t[now].son[ind]=++tot;
 39             upd(tot);
 40         }
 41         now=t[now].son[ind];
 42         if(i==len) t[now].mark=1;
 43     }
 44 }
 45 
 46 queue<int > q;
 47 void build_AC()
 48 {
 49     while(!q.empty()) q.pop();
 50     q.push(0);
 51     while(!q.empty())
 52     {
 53         int x=q.front();q.pop();
 54         for(int i=1;i<=10;i++) 
 55         {
 56             if(t[x].son[i])
 57             {
 58                 t[t[x].son[i]].fail=x?t[t[x].fail].son[i]:0;
 59                 q.push(t[x].son[i]);
 60             }
 61             else t[x].son[i]=t[t[x].fail].son[i];
 62         }
 63         if(t[t[x].fail].mark) t[x].mark=1;
 64     }
 65 }
 66 
 67 void init()
 68 {
 69     scanf("%s",ss+1);
 70     sl=strlen(ss+1);
 71     scanf("%d",&m);
 72     tot=0;upd(0);
 73     for(int i=1;i<=m;i++) read_trie();
 74     build_AC();
 75 }
 76 
 77 int check()
 78 {
 79     for(int i=1;i<=sl;i++)
 80     {
 81         bool p=1;
 82         int now=0;
 83         for(int j=i;j>=1;j--)
 84         {
 85             if(t[ t[now].son[ss[j]-'0'+1] ].mark) {p=0;break;}
 86             now=t[now].son[ss[j]-'0'+1];
 87         }
 88         if(!p) return i;
 89     }
 90     return 0;
 91 }
 92 
 93 int f[Maxn][Maxn];
 94 void dp()
 95 {
 96     memset(f,0,sizeof(f));
 97     for(int i=0;i<=tot;i++) f[0][i]=1;//走到i点，继续填0个数的方案
 98     
 99     for(int i=1;i<=sl;i++)
100     {
101         for(int j=0;j<=tot;j++) if(!t[j].mark)
102         {
103             for(int k=1;k<=10;k++) if(!t[t[j].son[k]].mark)
104              f[i][j]=(f[i][j]+f[i-1][t[j].son[k]])%Mod;
105         }
106     }
107 
108     int ans=0;
109     if(sl!=1)
110     {
111        for(int j=2;j<=sl;j++)
112        for(int i=2;i<=10;i++) if(!t[t[0].son[i]].mark) 
113         ans=(ans+f[sl-j][t[0].son[i]])%Mod;
114     }
115      
116     
117     int now=0;
118     bool ok=1;
119     for(int i=sl;i>=1;i--)
120     {
121         for(int k=0;k<ss[sl-i+1]-'0';k++)//枚举第i位填的数
122         {
123             if(i==sl&&k==0) continue;
124             if(t[t[now].son[k+1]].mark) continue;
125             ans=(ans+f[i-1][t[now].son[k+1]])%Mod;
126         }
127         now=t[now].son[ss[sl-i+1]-'0'+1];
128         if(t[now].mark) {ok=0;break;}
129     }
130     if(ok) ans=(ans+1)%Mod;
131     if(sl==1&&ss[1]=='0') ans=0;
132     printf("%d
",ans);
133 }
134 
135 int main()
136 {
137     init();
138     dp();
139     return 0;
140 }

[HDU3530]

2016-07-14 10:51:01

【HDU3530】 [Sdoi2014]数数 （AC自动机+数位DP）

3530: [Sdoi2014]数数

Description

Input

Output

Sample Input

Sample Output

HINT

【HDU3530】 [Sdoi2014]数数（AC自动机+数位DP）