C++14(g++5.4) 解法, 执行用时: 15ms, 内存消耗: 3048K, 提交时间: 2020-05-11 19:52:59

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=20020219;
int v[110],a[25];
ll dp[30][105][105],l,r;
int dfs(int pos,int pre,int num,int limit){
    if(num>v[pre]) return 0;
    if(pos==-1) return 1;
    if(!limit&&dp[pos][pre][num]!=-1) return dp[pos][pre][num];
    int up=limit?a[pos]:9;
    ll ret=0;
    for(int i=0;i<=up;i++){
        ret=(ret+dfs(pos-1,i,i==pre?num+1:1,limit&&i==a[pos]))%mod;
    }
    if(!limit) dp[pos][pre][num]=ret;
    return ret;
}
ll solve(ll x){
    int pos=0;
    while(x){
        a[pos++]=x%10;
        x/=10;
    }
    return dfs(pos-1,0,0,1);
}
int main(void)
{
    int t,n,x,y;
    cin>>t;
    while(t--){
        memset(v,0x3f,sizeof(v));
        memset(dp,-1,sizeof(dp));
        cin>>l>>r>>n;
        for(int i=1;i<=n;i++){
            cin>>x>>y;
            v[x]=min(v[x],y);
        }
        if(l)cout<<(solve(r)-solve(l-1)+mod)%mod<<endl;
        else cout<<solve(r)%mod<<endl;
    }
}

C++11(clang++ 3.9) 解法, 执行用时: 16ms, 内存消耗: 612K, 提交时间: 2020-04-03 09:43:21

#include<bits/stdc++.h>
using namespace std;
long long MOD=20020219,D[25][25][25],N[25],C[25];
long long DFS(int l,int x,int s,bool f)
{
	if(!l) return 1;
	if(!f&&D[l][x][s]) return D[l][x][s];
	long long i,j=f?N[l]:9,S=0;
	for(i=0;i<=j;i++)
	{
		if(i==x&&s+1>C[x]) continue;
		if(i==x) S=(S+DFS(l-1,i,s+1,f&&i==j))%MOD;
		else S=(S+DFS(l-1,i,1,f&&i==j))%MOD; 
	}
	return f?S:D[l][x][s]=S;
}
long long F(long long n)
{
	if(n==-1) return 0;
	int i=0;
	while(n) N[++i]=n%10,n/=10;
	return DFS(i,0,0,1); 
}
int main()
{
	long long T,l,r,n,x,len;
	scanf("%lld",&T);
	while(T--)
	{
		for(n=0;n<=9;n++) C[n]=21;
		memset(D,0,sizeof(D));
		scanf("%lld%lld%lld",&l,&r,&n);
		while(n--)
		{
			scanf("%lld%lld",&x,&len);
			C[x]=min(C[x],len);
		}
		printf("%lld\n",(F(r)-F(l-1)+MOD)%MOD);
	}
	return 0;
}