[SDOI2014]数数（ac自动机+数位DP）

佚名 6年前 (2019-05-16) 随笔 1014人围观抢沙发百度已收录

链接：https://ac.nowcoder.com/acm/problem/20366
来源：牛客网

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

输入描述:

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

输出描述:

输出一行一个整数，表示答案模1e⁹+7的值。
具体思路：首先考虑一下，我们在枚举位数的时候，不合法的情况是当前节点节点的val值为1或者这个节点的fail指针指向的节点在trie树上
的val值为1。然后我们就按照这个思路进行下去，对于每个节点我们求出他的fail指针，然后剩下的额就是数位DP的问题了。
AC代码：

 1 #include<bits/stdc++.h>  2 using namespace std;  3 # define ll long long  4 const int mod = 1e9+7;  5 const int maxn = 2e5+100;  6 char str_N[maxn],str[maxn];  7 int ch[maxn][12],val[maxn],fail[maxn];  8 int tot;  9 void add_trie(){ 10 int len=strlen(str); 11 int p=0; 12 for(int i=0; i<len; i++){ 13 int to=str[i]-'0'; 14 if(!ch[p][to]) 15 ch[p][to]=++tot; 16 p=ch[p][to]; 17  } 18 val[p]=1; 19 } 20 void get_fail(){ 21 queue<int>q; 22 q.push(0); 23 for(int i=0; i<=tot; i++) 24 fail[i]=-1; 25 while(!q.empty()){ 26 int top=q.front(); 27  q.pop(); 28 for(int i=0; i<10; i++){ 29 int to=ch[top][i]; 30 if(to){ 31  q.push(to); 32 int tmp=fail[top]; 33 while(tmp!=-1&&!ch[tmp][i]) 34 tmp=fail[tmp]; 35 fail[to]=(tmp==-1 ? 0 : ch[tmp][i]); 36 val[to]|=val[ch[fail[top]][i]];// 这里需要或上他的fail指针，只要有1就可以了。 37  } 38 else 39  { 40 ch[top][i]=ch[fail[top]][i]; // 注意这里的，每一颗数的节点都应为10个，如果在原来的trie树上没有这个节点，那么就继承这条链上合法的最后一个节点 41  } 42  } 43  } 44 } 45 int a[maxn]; 46 ll dp[2000+10][2000+10]; 47 ll dfs(int pos,int is_head,int is_zero,int p)// 注意前导0, 23的子串中不包含 023 48 { 49 if(!pos) 50 return val[pos]==0; 51 if(!is_head&&!is_zero&&dp[pos][p]!=-1) 52 return dp[pos][p]; 53 ll ans=0; 54 int fmax = is_head ? a[pos] : 9; 55 for(int i=0; i<=fmax; i++){ 56 if(is_zero&&i==0) 57 ans=(ans+dfs(pos-1,is_head&&i==fmax,1,0)%mod)%mod;// 从0开始 58 else{ 59 if(val[ch[p][i]])// 当当前节点非法的时候，停止搜索 60 continue; 61 ans=(ans+dfs(pos-1,is_head&&i==fmax,is_zero&&i==0,ch[p][i])%mod)%mod; 62  } 63  } 64 if(!is_head&&!is_zero) 65 dp[pos][p]=ans; 66 return ans; 67 } 68 ll solve() 69 { 70 memset(dp,-1,sizeof(dp)); 71 int len=strlen(str_N); 72 reverse(str_N,str_N+len); 73 for(int i=0; i<len; i++){ 74 a[i+1]=str_N[i]-'0'; 75  } 76 return dfs(len,1,1,0); 77 } 78 int main(){ 79 scanf("%s",str_N);// 输入的是按照自字符串读入 80 int m; 81 scanf("%d",&m); 82 while(m--){ 83 scanf("%s",str); 84  add_trie(); 85  } 86  get_fail(); 87 ll ans=solve()-1; 88 printf("%lld\n",ans); 89 return 0; 90 }