求助
查看原帖
求助
800499
suzhikz楼主2023/9/5 15:08
#include<iostream>
#include<cmath>
#include<iomanip>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<queue>
#include<vector>
#include<stdio.h>
//#include<map>
#include<string.h>
#include<time.h>
#include<stdlib.h>
#include<bitset>
using namespace std;
const int mod=1000000007; 
long long dp[30][10],power[30];
void init(){
	for(int i=0;i<=9;i++)dp[1][i]=i;
	power[0]=1;
	for(int i=1;i<=18;i++)power[i]=power[i-1]*10%mod;
	for(int i=2;i<=18;i++){
		for(int j=0;j<=9;j++){
			dp[i][j]=power[i-1]*j%mod;
			for(int k=0;k<=9;k++)dp[i][j]+=dp[i-1][k]; 
            dp[i][j]%=mod;
		}
	} 
}
int a[30];
long long ask(long long x){
	memset(a,0,sizeof(a));
	int w=0;
	long long ans=0;
	while(x){
		a[++w]=x%10;
		x=x/10;
	}
	for(int i=1;i<w;i++){
		for(int j=1;j<=9;j++){
			ans=(ans+dp[i][j])%mod;
		}
	}
	for(int i=1;i<a[w];i++)ans=(ans+dp[w][i])%mod;
	int sum=a[w];
	for(int i=w-1;i>=1;i--){
		ans+=sum*power[i-1]*a[i]%mod;
		for(int j=0;j<=a[i];j++){
			ans=(ans+dp[i][j])%mod;
		}
		sum+=a[i];
	}
	return ans;
}
int main(){
	init();
	int t;
	cin>>t;
	while(t--){
		long long l,r;
		cin>>l>>r;
		cout<<(ask(r+1)-ask(l)+mod)%mod;
	}
	
	return 0;
}

2023/9/5 15:08
加载中...