数位DP板子90pts。
查看原帖
数位DP板子90pts。
346245
P32sx楼主2023/1/11 17:04
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long LL;
const int N = 20, mod = 1e9 + 7;
int T;
int num[N];
LL f[N];
int dfs(int pos, bool lim, bool zero){
	if(!pos) return 0;
	if(!lim && !zero && f[pos]) return f[pos];
	LL res = 0;
	int minn = zero ? 1 : 0, maxn = lim ? num[pos] : 9;
	for(int i = minn; i <= maxn; i++){
		if(lim && i == maxn){
			LL t = 0;
			for(int j = pos - 1; j; j--)
				t = t * 10 + num[j];
			t = (t + 1) % mod;
			res += t * i, res %= mod;
		} else res += i * pow(10, pos - 1), res %= mod;
		res += dfs(pos - 1, lim && i == maxn, false), res %= mod;
	}
	if(zero) res += dfs(pos - 1, false, zero), res %= mod;
	if(!lim) f[pos] = res;
	return res;
}
inline int F(LL x){
	memset(f, 0, sizeof f);
	int len = 0;
	for(; x; x /= 10)
		num[++ len] = x % 10;
	return dfs(len, true, true);
}
signed main(){
	cin >> T;
	while(T --){
		LL l, r;
		cin >> l >> r;
		cout << (F(r) - F(l - 1) + mod) % mod << endl;
	}
	return 0;
}
2023/1/11 17:04
加载中...