考虑统计出每一个数位的出现次数,然后乘i求和
#include <bits/stdc++.h> #define int long long using namespace std ; const int ha = 1e9+7 ; int T ; int l , r ; int f[20] , ten[20] , cnta[20] , cntb[20] ,num[20] ; void work(int x, int cnt[]) { int len = 0 ; while(x) { num[++len] = x % 10 ; x /= 10 ; } for(int i = len ; i >= 1 ; i --) { for(int j = 0 ; j <= 9 ; j ++) { cnt[j] =(cnt[j] + f[i-1]*num[i]%ha)%ha ; //求出除了最高位以外的所有数的和 } for(int j = 0 ; j < num[i] ; j ++) { cnt[j] = (cnt[j] + ten[i-1] )%ha;//求出最高位单个数字的出现次数 } int num2 = 0 ; for(int j = i-1 ; j >= 1 ; j --) { num2 = (num2 * 10 + num[j])%ha ;//加上最高位的数字出现个数 } cnt[num[i]] = (cnt[num[i]]+num2 + 1)%ha ; cnt[0] = (cnt[0]- ten[i-1]+ha)%ha ; } } signed main () { scanf("%lld",&T) ; ten[0] = 1 ; for(int i = 1 ; i <= 19 ; i ++) { f[i] = f[i-1] * 10 + ten[i-1] ; ten[i] = ten[i-1]*10 ; } while(T --) { scanf("%lld%lld",&l,&r) ; work(r,cnta) ; work(l-1,cntb) ; int ans = 0 ; for(int i = 0 ; i <= 9 ; i ++) { ans = (ans+(cnta[i]-cntb[i]+ha)*i%ha)%ha ; } memset(cnta,0,sizeof(cnta)) ; memset(cntb,0,sizeof(cntb)) ; printf("%lld\n",(ans+ha)%ha) ; } return 0 ; }