WA#12 公式法 求助
查看原帖
WA#12 公式法 求助
105925
Kari5307_yu楼主2020/8/14 21:09

思路:对于00~x999x9999999,可以通过首尾配对推出公式,然后递推做就好了

#include<bits/stdc++.h>
#define int long long
#define pow qpow
using namespace std;
int qpow(int x,int y){
	int s=1;
	for(int i=1;i<=y;i++)
		s*=x,s%=1000000007;
	return s;
}
int helper(int x){
	if(x<=9)return (x+1)*x/2;
	int xx=x,s=0,a=0;;
	while(xx){
		s++;
		a=xx%10;
		xx/=10;
	}
	//printf("%lld %lld\n",x,((a-1+9*(s-1))%1000000007*a%1000000007*5%1000000007*pow(10,s-2)%1000000007+a*(x%1000000007-a*pow(10,s-1)%1000000007+1000000007+1)%1000000007));
	return (((a-1+9*(s-1))%1000000007*a%1000000007*5%1000000007*pow(10,s-2)%1000000007+a*(x%1000000007-a*pow(10,s-1)%1000000007+1000000007+1)%1000000007)+helper(x-a*pow(10,s-1)))%1000000007;
}
signed main(){
	int T,l,r;
	scanf("%lld",&T);
	while(T--){
		scanf("%lld%lld",&l,&r);
		printf("%lld\n",(helper(r)-helper(l-1)+1000000007)%1000000007);
	}
	return 0;
}
2020/8/14 21:09
加载中...