刚学数位DP,求助。 样例过了!
查看原帖
刚学数位DP,求助。 样例过了!
311502
逸之为一楼主2021/1/4 22:01
#include<bits/stdc++.h>
using namespace std;
long long a[1000100];
long long dp[200][200];
long long n;
long long x,y;
long long dfs(int m,int ti,int s){
	long long ans=0;
	if(m==-1) return s;
	if(!ti && dp[m][s]!=-1ll) return dp[m][s]; 	
	int r;
	if(ti) r=a[m];
	else r=9;
	for(int i=0;i<=r;i++){
		if(i==a[m] && ti) ans=(ans+dfs(m-1,1,s+i))%1000000007;
		else ans=(ans+dfs(m-1,0,s+i))%1000000007;
	}
	if(!ti) dp[m][s]=ans;
	return ans;
}
long long cmp(int x){	
	for(int i=0;i<=199;i++) for(int j=0;j<=199;j++) dp[i][j]=-1ll;	
	int k=0;
	while(x){
		a[k++]=x%10;
		x=x/10;
	}
	return dfs(k-1,1,0)%1000000007;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x>>y;
		long long x1=cmp(x-1);
		long long y1=cmp(y);
		cout<<(y1-x1)%1000000007<<endl;
	}
	return 0;
} 
2021/1/4 22:01
加载中...