https://www.lydsy.com/JudgeOnline/problem.php?id=3530
我们称一个正整数N是幸运数，当且仅当它的十进制表示中不包含数字串集合S中任意一个元素作为其子串。例如当S=(22，333，0233)时，233是幸运数，2333、20233、3223不是幸运数。
给定N和S，计算不大于N的幸运数个数。
参考：https://www.luogu.org/blog/user17952/solution-p3311
绝对（对我来说）是道难题，尤其是很久不写AC自动机与数位dp的我……
首先n特别大，必须得考虑数位dp。
其次给了一堆串，要求不能出现这些串，先建AC自动机再说。
于是得出了一个愉快的结论：在AC自动机上跑数位dp（写到这里我只想用CaO来表达我的心情）
设$f[i][j][0/1]$为填到$i$数位，当前在AC自动机的$j$节点处，已经小于等于/大于到$i$位的原数。
此时需要注意：为了方便（因为参考是这么写的233），我们正着扫n而非以前的套路倒着扫n，这样做会带来一些问题，于是我们将小于等于也拆开，分别用0和1表示。
（PS：那么反着扫不知道是否可行……以及如果要反着扫的话可能需要反着存串。）
dp式子就不细讲了，直接看代码理解吧。唯一要注意的是不能有前导0所以第一层我们要特殊处理。
#include<map> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<cctype> #include<vector> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int p=1e9+7; const int L=1505; struct AC{ int fail,a[10]; bool ed; }tr[L]; char s[L],s0[L]; int tot,f[L][L][3]; void insert(){ int len=strlen(s),now=0; for(int i=0;i<len;i++){ int w=s[i]-'0'; if(!tr[now].a[w])tr[now].a[w]=++tot; now=tr[now].a[w]; } tr[now].ed=1; } void getfail(){ queue<int>q; tr[0].fail=0; for(int i=0;i<10;i++){ int u=tr[0].a[i]; if(u){ tr[u].fail=0;q.push(u); } } while(!q.empty()){ int u=q.front();q.pop(); for(int i=0;i<10;i++){ if(tr[u].a[i]){ int v=tr[u].a[i]; tr[v].fail=tr[tr[u].fail].a[i]; tr[v].ed|=tr[tr[tr[u].fail].a[i]].ed; q.push(v); }else tr[u].a[i]=tr[tr[u].fail].a[i]; } } } inline int add(int x,int y){ x+=y;if(x>=p)x-=p;return x; } int main(){ int n,m; scanf("%s%d",s0,&m); while(m--){ scanf("%s",s);insert(); } getfail(); n=strlen(s0); int ans=0; for(int i=1;i<10;i++){ int v=tr[0].a[i],w=s0[0]-'0'; if(!tr[v].ed){ if(i<w)f[0][v][0]++; else if(i==w)f[0][v][1]++; else f[0][v][2]++; } } for(int i=1;i<n;i++){ int w=s0[i]-'0'; for(int j=0;j<=tot;j++){ if(f[i-1][j][0]||f[i-1][j][1]||f[i-1][j][2]) for(int k=0;k<10;k++){ int v=tr[j].a[k]; if(tr[v].ed)continue; if(k<w){ f[i][v][0]=add(f[i][v][0],add(f[i-1][j][0],f[i-1][j][1])); f[i][v][2]=add(f[i][v][2],f[i-1][j][2]); }else if(k==w){ f[i][v][0]=add(f[i][v][0],f[i-1][j][0]); f[i][v][1]=add(f[i][v][1],f[i-1][j][1]); f[i][v][2]=add(f[i][v][2],f[i-1][j][2]); }else{ f[i][v][0]=add(f[i][v][0],f[i-1][j][0]); f[i][v][2]=add(f[i][v][2],add(f[i-1][j][2],f[i-1][j][1])); } } } } for(int i=0;i<n;i++){ for(int j=0;j<=tot;j++){ ans=add(ans,add(f[i][j][0],f[i][j][1])); if(i<n-1)ans=add(ans,f[i][j][2]); } } printf("%d ",ans); return 0; }
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/ +
+++++++++++++++++++++++++++++++++++++++++++