题意：
求区间中，满足限制条件的数字的个数。 限制条件就是某些数字不能连续出现几次。
思路：
比较裸的数位DP， DP数组开一个dp【len】【x】【cnt】 表示长度为len，x这个数字连续出现cnt次的个数。
#include#include #include #include #include typedef long long ll;using namespace std;const int mod = 20020219; int dp[22][11][22]; int cnt[11],shu[22]; ll swdp(int len, int x,int sum, bool limit){ if(len == 0)return 1; if(!limit && dp[len][x][sum]) return dp[len][x][sum]; int mx = limit ? shu[len] : 9; ll res = 0; for(int i=0; i<=mx; i++){ if(x==i && sum + 1 > cnt[x])continue; if(x==i) res = (res + swdp(len-1,x,sum+1, limit && i == mx)) % mod; else res = (res + swdp (len-1,i,1,limit && i == mx))%mod; } return limit?res:dp[len][x ][sum] = res; } ll solve(ll x){ if(x == -1)return 0; int k = 0; while(x > 0){ shu[++k] = x % 10; x /= 10; } return swdp(k, 0, 0, true); }int main(){ int t,n; scanf("%d", &t); ll le,ri; while(t--) { for(int i=0; i<=9; i++)cnt[i] = 21; memset(dp,0,sizeof(dp)); scanf("%lld%lld%d", &le, &ri, &n); while(n--) { int x,len; scanf("%d%d", &x, &len); cnt[x] = min(cnt[x] , len); } printf("%lld\n", (solve(ri) - solve(le-1) + mod)%mod); } return 0;}