90分WA #18 #20 求调
查看原帖
90分WA #18 #20 求调
1406565
LYD12345楼主2025/1/23 13:47
#include <bits/stdc++.h>
using namespace std;

const unsigned long long mod=1000000007;

unsigned long long l,r;

unsigned long long c[101];
unsigned long long f[101];
unsigned long long ans[101];

unsigned long long solve(unsigned long long n){
	
	if(n==0)	return 0;
	
	//f[i]表示10的i次幂
	f[0]=1;
	for(unsigned long long i=1;i<=16;i++){
		f[i]=f[i-1]*10;
		f[i]%=mod;
	}
	
	unsigned long long s=0;
	for(unsigned long long i=n;i;i/=10){
		c[++s]=i%10;
		c[s]%=mod;
	}
	for(unsigned long long i=1,j=s;i<j;i++,j--){
		swap(c[i],c[j]);
	}
	
	memset(ans,0,sizeof(ans));
	unsigned long long res=0;
	for(unsigned long long i=1;i<=s;i++){//i枚举前i-1位与n不同的数
		for(unsigned long long j=1;j<i;j++){//前i-1位
			res%=mod;res+=c[j]%mod*c[i]%mod*f[s-i]%mod;res%=mod;
		}
		for(unsigned long long j=1;j<c[i];j++){//枚举第i位的值
			res%=mod;res+=j%mod*f[s-i]%mod;res%=mod;
		}
		if(i!=s){
			for(unsigned long long j=1;j<=9;j++){//后s-i位
				res%=mod;res+=j%mod*(s-i)%mod*c[i]%mod*f[s-i-1]%mod;res%=mod;
			}
		}
	}
	//n本身算进去
	for(unsigned long long i=n;i;i/=10){
		res%=mod;ans[i%10]++;ans[i%10]%=mod;
	}
	for(unsigned long long j=1;j<=9;j++){
		res%=mod;res+=ans[j]%mod*j%mod;res%=mod;
	}
	
	return res%mod;
	
}

int main(){
	
	unsigned long long t;
	scanf("%llu", &t);
	while(t--){
		scanf("%llu%llu", &l, &r);
		unsigned long long an=(solve(r)%mod+mod-solve(l-1)%mod)%mod;
		printf("%llu\n", an);
	}
	
	
	return 0;//痛苦地完成程序
	
}
2025/1/23 13:47
加载中...