分析

我们把数字考虑为字符串，那么现在我们就是要求出有多少方案满足 没有出现在 串中。

• 关于这道题，因为我们要对子串考虑，比较自然考虑到 树和 。由于 并不能很好处理失配的问题，那么考虑 自动机。我们定义 其中 表示，该节点为一个 的结尾，那么当我们转移到这个点的时候是非法的。但是在 自动机上不知每个串的插入的地方是非法的，如果串 是 的子串，而且 ，那么 。而 指针指向的就是一个串的最长后缀，所以我们才考虑到 。

• 那么现在我们处理了子串的合法性，定义 为已经考虑长度为 ，当前节点为 的合法答案，那么 ，现在考虑我们构成的串 在数值上要小于等于 。那么这个可以很好的数位 。从而限制我们转移。细节还是见代码，要注意没有前导零的时候不能转移到 上的其他节点，因为这个时候我们的串还没开始。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1600,mod = 1e9 + 7;
int f[1300][N][2][2],fail[N],ch[N][10],val[N],size;
int n;
char m[1300];
void insert(char *S) {
    int len = strlen(S + 1),u = 0;
    for(int i = 1;i <= len;i++) {
        int c = (S[i] - '0');
        if(!ch[u][c]) ch[u][c] = ++size;
        u = ch[u][c];
    }val[u] |= 1;
}
void build() {
    queue<int> Q;
    for(int i = 0;i < 10;i++) if(ch[0][i]) Q.push(ch[0][i]);
    while(!Q.empty()) {
        int x = Q.front();Q.pop();
        for(int i = 0;i < 10;i++) {
            int y = ch[x][i];
            if(y) {fail[ch[x][i]] = ch[fail[x]][i];val[y] |= val[fail[y]];Q.push(y);}
            else ch[x][i] = ch[fail[x]][i];
        }
    }
}
void inc(int &x,int y) {x = (x + y) % mod;}
int dfs(int now,int pos,int limit,int st) {
    if(now <= 0) return !val[pos];
    if(val[pos]) return 0;
    if(f[now][pos][limit][st] != -1) return f[now][pos][limit][st]; 
    int x = limit ? (m[now] - '0') : 9,res = 0;
    for(int i = 0;i <= x;i++) {
        inc(res, dfs(now - 1,(st && (i == 0)) ? 0 : ch[pos][i],(limit && (i + '0' == m[now])),(st && (i == 0))) );
    }
    return f[now][pos][limit][st] = res;
}
int main() {
    scanf("%s%d",m + 1,&n);
    int len = strlen(m + 1);
    for(int i = 1;i <= n;i++) {
        static char S[N];scanf("%s",S + 1);insert(S);
    }
    build();reverse(m + 1,m + 1 + len);
    memset(f,-1,sizeof(f));
    int ans = dfs(len,0,1,1);inc(ans,mod - 1);
    cout << ans << endl;return 0;
}