C++(clang++11) 解法, 执行用时: 246ms, 内存消耗: 36312K, 提交时间: 2021-03-06 18:42:35

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
char s[2110][2110],n[2110];
int fail[2110];
int tr[2110][30];
int vis[2110],a[11000]; 
int len,m,tot=1;
int f[2110][2110];
int dfs(int pos,int ac,bool limit,bool ling)
{
	if(vis[ac]) return 0;
	if(pos==len+1) return 1;
	int gao=limit?a[pos]:9;
	if(f[pos][ac]!=-1&&!limit&&!ling) return f[pos][ac];
	int tmp=0;
	for(int i=0;i<=gao;i++)
		tmp=(tmp+dfs(pos+1,(ling&&(i==0))?ac:tr[ac][i],limit&&(i==gao),ling&&(i==0)))%mod;
	if(!limit&&!ling) f[pos][ac]=tmp;
	return tmp%mod;
}
int work(char *x)
{
	len=strlen(x+1);
	for(int i=1;i<=len;i++) a[i]=x[i]-'0';
	return dfs(1,1,1,1)%mod;
}

signed main()
{
	memset(f,-1,sizeof(f)); 
	scanf("%s",n+1);
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		scanf("%s",s[i]+1);
		int u=1; 
		for(int j=1;s[i][j];j++)
		{
			if(!tr[u][s[i][j]-'0']) tr[u][s[i][j]-'0']=++tot;
			u=tr[u][s[i][j]-'0'];
		}
		vis[u]=1;
	}
    for(int i=0;i<=9;i++) tr[0][i]=1;
    queue <int> q;
    q.push(1);
    while(!q.empty())
	{
		int p=q.front();
		q.pop();
		for(int i=0;i<=9;i++)
		{
			if(tr[p][i])
			{
				fail[tr[p][i]]=tr[fail[p]][i];
				vis[tr[p][i]]|=vis[fail[tr[p][i]]];
				q.push(tr[p][i]);
			}
			else tr[p][i]=tr[fail[p]][i];
		}
	}
	cout<<(work(n)-1+mod)%mod<<endl;
}