C++11(clang++ 3.9) 解法, 执行用时: 42ms, 内存消耗: 6500K, 提交时间: 2019-03-31 15:22:58

#include<bits/stdc++.h>
using namespace std;const int N=107,mod=998244353;
int a[N][10],nxt[N],n,i,j,m,t,w,val[N],q[N],sz=1,bin[N],top;typedef pair<int,int> pa;pa dp[N][N][33][2];char A[N],B[N],s[N];
void ins(int id){
	int now=1;for(int i=0,c;s[i];++i){
		c=s[i]-'0';if(!a[now][c])a[now][c]=++sz;now=a[now][c];
	}val[now]|=id;
}
void acmach(){
	for(int i=0;i<10;++i)a[0][i]=1;
	t=0;w=1;q[0]=1;
	while(t!=w){
		int x=q[t++];
		for(int i=0;i<10;++i)if(a[x][i]){
			nxt[a[x][i]]=a[nxt[x]][i];val[a[x][i]]|=val[nxt[a[x][i]]];q[w++]=a[x][i];
		}else a[x][i]=a[nxt[x]][i];
	}
}
pa dfs(int x,int cur,int S,int pre,int flag){
	if(x==0){if(S==m)return pa(1,0);else return pa(0,0);}
	if(!flag&&dp[x][cur][S][pre].first!=-1)return dp[x][cur][S][pre];
	int mx=flag?q[x]:9;pa res(0,0),tmp;
	for(int i=0;i<=mx;++i){
		if(i==0&&pre&&x!=1){
			tmp=dfs(x-1,cur,S,pre,flag&&i==mx);
		}
		else tmp=dfs(x-1,a[cur][i],S|val[a[cur][i]],pre&&i==0,flag&&i==mx);
		res.first=(res.first+tmp.first)%mod;
		res.second=(res.second+tmp.second+1LL*tmp.first*i%mod*bin[x-1]%mod)%mod;
	}
	if(!flag)dp[x][cur][S][pre]=res;
	return res;
}
void go(string&s)
{reverse(s.begin(),s.end());while(s.size()>1&&s.back()=='0')s.pop_back();reverse(s.begin(),s.end());}
int check(string s){
	go(s);
	int res=0,cur=1;int ans=0;
	for(int i=0;i<s.size();++i)ans+=1LL*(s[i]-'0')*bin[s.size()-i-1]%mod,ans%=mod,res|=val[a[cur][s[i]-'0']],cur=a[cur][s[i]-'0'];
	return res==m?ans:0;
}
int cal(string s){
	go(s);top=0;
	for(i=s.size()-1;i>=0;--i)q[++top]=s[i]-'0';
	return dfs(top,1,0,1,1).second;
}
int main(){
	memset(dp,-1,sizeof(dp));
	for(bin[0]=1,i=1;i<N;++i)bin[i]=1LL*bin[i-1]*10%mod;
	for(scanf("%d%s%s",&n,A,B),m=(1<<n)-1;n--;)scanf("%s",s),ins(1<<n);acmach();
	printf("%lld\n",((0LL+cal(B)-cal(A)+check(A))%mod+mod)%mod);
}