题目描述
有一天clccle在家里玩手机,突然手机上出现了一个诡异的黑影,眼里闪烁着白光,发出了奇怪的声音(像是正常的声音倒放之后再正放的样子),clccle努力辨别后终于听懂了这个黑影在说什么,大概如下,给定你一个区间[l,r]和多个约束,
请你求出在这个区间内满足这个约束的数字个数(不含前导零),如果clccle不能在1s内求出这个答案,就会被送入一个奇怪的旅馆(Rusty Lake Hotel),因为clccle很害怕,请你帮她在1s之内求出这个答案

输入描述:
注意:此题有多组数据

第一行,一个整数T,代表数据组数

对于每组数据,

有三个数字 l,r,n

接下来n行，每行一个数字x，接下来一个数len表示数字x在数字串中连续出现的次数不能大于len
输出描述:
对于每组数据

输出一个整数,表示l,r中满足约束的数字个数。(对20020219取模)
示例1
输入
复制
2
0 50 2
4 1
4 4
0 100 2
4 1
5 1
输出
复制
50
99
备注:
数据保证没有对数字0的限制( •̀ ω •́ )✧Ǜ

对于全部数据:1<=T<=50,0<=l<r<=1e18,1<=n<=100

数位dp+约束取min

我们从题目中可以看到，对许多数字都有约束不止一个数字，并且区间长的必然受区间小的所影响，所以我们用一个数组表示当前的数字的最小约束。

然后每次数位dp转移即可，每次看当前的数字连续个数已经大于了约束即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int p=20020219;
int T,dp[20][10][20],a[20],pos,x,len,vis[10];
int dfs(int pos,int pre,int cnt,int limit){
	if(vis[pre]<cnt)	return 0;
	if(!pos)	return 1;
	if(!limit&&dp[pos][pre][cnt]!=-1)	return dp[pos][pre][cnt];
	int up=limit?a[pos]:9,res=0;
	for(int i=0;i<=up;i++){
		res=(res+dfs(pos-1,i,(i==pre)?cnt+1:1,limit&&i==up))%p;
	}
	if(!limit)	dp[pos][pre][cnt]=res;
	return res;
}
int solve(int x){
	int pos=0;
	while(x)	a[++pos]=x%10,x/=10;
	return dfs(pos,-1,0,1);
}
signed main(){
	cin>>T;
	while(T--){
		int l,r,n;	cin>>l>>r>>n;	memset(vis,0x3f,sizeof vis);
		memset(dp,-1,sizeof dp);
		while(n--){
			cin>>x>>len;	vis[x]=min(vis[x],len);
		}
		if(l)	cout<<(solve(r)-solve(l-1)+p)%p<<endl;
		else	cout<<solve(r)%p<<endl;
	}
	return 0;
}