70 pts 求助,悬关
查看原帖
70 pts 求助,悬关
490978
小超手123楼主2023/5/27 16:55
#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
using namespace std;
int num, d, Q;
int a[30], f[15][205][2]; 
//f[i][j][0/1]:第i位, 目前和, 上一位 到/没到 上界 
int DFS(int pos, int cnt, int lim) {
    if(pos == num + 1) return cnt % mod;
	if(f[pos][cnt][lim] != -1) return f[pos][cnt][lim];
	int ans = 0;
	for(int v = 0; v <= (lim ? a[pos] : 9); v++) 
		ans = (ans + DFS(pos + 1, cnt + v, lim && v == a[pos])) % mod;
    return f[pos][cnt][lim] = ans;
}
int Sol(int x) {
    num = 0;
    memset(f, -1, sizeof(f)); 
    while(x) {
        a[++num] = x % 10;
        x /= 10;
	}
	reverse(a + 1, a + num + 1);
	DFS(1, 0, 1);
}
signed main() {
    cin >> Q;
    while(Q--) {
        int x, y;
        cin >> x >> y;
        cout << (Sol(y) % mod - Sol(x - 1) % mod + mod)% mod << endl;
	}
    return 0;
}
2023/5/27 16:55
加载中...