60pts求助!!!
查看原帖
60pts求助!!!
1015780
newbieTroll楼主2023/11/17 20:04
#include<bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
#define int long long
int l,r;
int dp[100][100];
int a[100];
int dfs(int pos,int lim,int sum){
	int up,res=0;
	if(!pos) return sum;
	if(!lim&&dp[pos][sum]!=-1) return dp[pos][sum];
	up=lim?a[pos]:9;
	for(int i=0;i<=up;++i){
		res+=dfs(pos-1,lim&&i==a[pos],sum+i);
	}
	dp[pos][sum]=res;
	return res;
}
int check(int n){
	memset(a,0,sizeof(a));
	memset(dp,-1,sizeof(dp));
	int pos=0;
	while(n){
		a[++pos]=n%10;
		n/=10;
	}
	int a=0,ans=0;
	return dfs(pos,1,0);
}
signed main(){
	int t;
	cin>>t;
	while(t--){
		cin>>l>>r;
		cout<<(check(r)-check(l-1)+MOD)%MOD<<endl;
	}
	
    return 0;
}
2023/11/17 20:04
加载中...