#题目描述
#做法
AC自动机+DP
我们用\(f_{i,j,f}\)表示当前是第\(i\)位，在自动机的状态\(j\)上，\(f\)用串的前缀是否等于\(N\)的前缀
假设\(k\in [0,10)\),\(v=next[j][k]\)
\[f_{i+1,v,0}=\sum\left\{\begin{array}{ll}f_{i+1,j,0} && \forall k\in [0,10)\\f_{i+1,j,1} && k<N_i\end{array}\right.\] \[f_{i+1,v,1}=\sum f_{i+1,j,1},k=N_i\]最后答案就是
\[\sum f_{\mathrm{len}(N),j,0}+f_{\mathrm{len}(N),j,1}\]这里有一个问题，就是如果给定的字符串集合\(S\)含有前导0，那么我们就会发现，本来表示不存在的0这里突然被占用，导致大量合法的“幸运数”被判为非法
我的做法是，建立一个超级起点\(SS\)，它的状态转移是像下面这个表这样的：
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
fail |
|---|---|---|---|---|---|---|---|---|---|---|
SS |
S.1 |
S.2 |
S.3 |
S.4 |
S.5 |
S.6 |
S.7 |
S.8 |
S.9 |
S |
注意加粗的部分，可以看出，这个超级起点除了对0的输入不一样之外，其余的全部一样，从而0就被困在里面，不会被计入答案，同时，如果想离开超级起点，就必须给予一个非零输入，进入别的点，这样就相当于删除了所有的前导0
完美解决问题
另外，这题的数据中，有8个点的S集合里的数是不带前导0的，由此我们可以看出出题人的良苦用心
#AC Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
struct TrieNode{
int flag,fail,next[10];
}T[1505];
int f[1205][1505][2];
int root=1;
int tT=1;
const int mod=1000000007;
void trieInsert(char *numb)
{
int len=strlen(numb);
int p=root;
for (int i=0;i<len;i++)
{
if (T[p].next[numb[i]-'0']==0)
T[p].next[numb[i]-'0']=++tT;
p=T[p].next[numb[i]-'0'];
}
T[p].flag=true;
}
void trieBuild()
{
int u,v;
queue<int>Q;
T[root].fail=0;
Q.push(root);
while (!Q.empty())
{
u=Q.front();Q.pop();
for (int i=0;i<10;i++)
{
if (T[u].next[i])
{
if (u==root)
{
T[T[u].next[i]].fail=root;
}
else
{
v=T[u].fail;
while (v)
{
if (T[v].next[i])
{
T[T[u].next[i]].fail=T[v].next[i];
break;
}
v=T[v].fail;
}
if (!v)
T[T[u].next[i]].fail=root;
}
Q.push(T[u].next[i]);
}
}
}
}
int matchAndDp(char *N,bool flag)
{
int len=strlen(N),v;
f[0][tT][1]=1;
for (int i=0;i<len;i++)
{
for (int j=1;j<=tT;j++)
{
if (T[j].flag)
continue;
for (int k=0;k<10;k++)
{
v=j;
while (v!=root && T[v].next[k]==0)
v=T[v].fail;
v=T[v].next[k];
if (v==0)
v=root;
if (T[v].flag)
continue;
if (k<N[i]-'0')
{
(f[i+1][v][0]+=(f[i][j][0]+f[i][j][1])%mod)%=mod;
}else if (k==N[i]-'0')
{
(f[i+1][v][0]+=f[i][j][0])%=mod;
(f[i+1][v][1]+=f[i][j][1])%=mod;
}else if (k>N[i]-'0')
{
(f[i+1][v][0]+=f[i][j][0])%=mod;
}
}
}
}
int ans=0;
for (int i=1;i<tT;i++)
if (T[i].flag==false)
(ans+=((f[len][i][0]+f[len][i][1])%mod))%=mod;
return ans;
}
int main()
{
char NN[1205],buf[1505];
int m;
memset(T,0,sizeof(T));
scanf("%s%d",NN,&m);
for (int i=1;i<=m;i++)
{
scanf("%s",buf);
trieInsert(buf);
}
trieBuild();
tT++;
T[tT].next[0]=tT;
T[tT].fail=root;
for (int i=1;i<10;i++)
T[tT].next[i]=T[root].next[i];
int len=strlen(NN);
int ans=0;
(ans+=matchAndDp(NN,1))%=mod;
printf("%d\n",ans);
return 0;
}