45pts求调,悬赏一个关注
查看原帖
45pts求调,悬赏一个关注
374769
Epi4any楼主2022/9/12 22:53
#include<iostream>
#include<cstring>
using namespace std;

#define MAXN 205
#define MOD 1000000007
#define ll long long

ll t[MAXN];
struct data {
	ll a[105];
};

data operator + (const data &a, const data &b) {
	data ans;
	for (int i = 0; i <= 9; i++) ans.a[i] = (a.a[i] + b.a[i])%MOD;
	return ans;
}

data ans1, ans2, dp[MAXN][MAXN];

data cal(ll a) {
	int len = 0, x[MAXN];
	data res;
	ll tmp = a;
	while (tmp) { 
		x[++len] = tmp % 10;
		tmp /= 10;
	}
	for (int i = 0; i <= 9; i++) res.a[i] = 0;
	res.a[0]++;   
	if (a == 0) return res;
	for (int i = 1; i < len; i++)
		for (int j = 1; j <= 9; j++)
			res = (res + dp[i][j]);   
	for (int i = len; i; i--) {  	
		for (int j = (i == len ? 1 : 0); j < x[i]; j++) res = (res + dp[i][j]);
		a %= t[i];
		res.a[x[i]] += a + 1;
	}
	return res;
}

ll a, b, T;

void solve() {
	scanf("%lld%lld", &a, &b);
	t[1] = 1;
	
	for (int i = 2; i <= 12; i++) t[i] = 10 * t[i - 1]%MOD;
	for (int i = 0; i <= 9; i++) dp[1][i].a[i] = 1;

	for (int i = 2; i <= 12; i++) for (int j = 0; j <= 9; j++) {
		for (int k = 0; k <= 9; k++) dp[i][j] = (dp[i][j] + dp[i - 1][k]);
		dp[i][j].a[j] += t[i];
	}

	ans1 = cal(b);
	ans2 = cal(a - 1);
	
    long long ans=0;
	for (int i = 0; i <= 9; i++)
		ans+=(ans1.a[i] - ans2.a[i])*i%MOD;
    cout<<ans<<endl;
}

int main() {
    cin >> T;
    while (T--) {
        memset(dp,0,sizeof(dp));
        memset(t,0,sizeof(t));
        solve ();
    }
    return 0;
}

RE*8+WA*3

奖励关注将来自 @GSShacker

2022/9/12 22:53
加载中...