45pts求调
查看原帖
45pts求调
764574
hmy0213楼主2024/10/10 12:53
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const ll P=1e9+7;
ll l,r,len,num,anss,a[105],dp[205][205][4][4];
ll dfs(int pos,int cnt,int limit,int fax){
	if(pos==len) return cnt;
	if(dp[pos][cnt][limit][fax]!=-1) return dp[pos][cnt][limit][fax];
	ll ans=0;
	for(int i=0;i<=(limit?a[pos]:9);i++){
		if(!fax&&!i) ans+=((dfs(pos+1,cnt,limit&&i==a[pos],0)+P)%P+P)%P;
		else ans+=((dfs(pos+1,cnt+(i==num),limit&&i==a[pos],1)+P)%P+P)%P;  
	}
	return dp[pos][cnt][limit][fax]=ans;
}
ll slove(ll x){
	memset(dp,-1,sizeof(dp));
	memset(a,0,sizeof(a));
	len=0;
	while(x){
		a[len++]=x%10;
		x/=10;
	}
	reverse(a,a+len);
	return dfs(0,0,1,0);
} 
int main(){
	int T;
	cin>>T;
	while(T--){
		cin>>l>>r;
		anss=0;
		for(ll i=1;i<=9;i++){
			num=i;
			anss+=((i*(slove(r)-slove(l-1))+P)%P+P)%P;
		}
		cout<<anss<<endl;
	}
	
	return 0;
}
2024/10/10 12:53
加载中...