数位dp90分求助,死活调不出来了
查看原帖
数位dp90分求助,死活调不出来了
526677
封禁用户楼主2022/6/10 10:30
#include<bits/stdc++.h>
using namespace std;
#define N 114514
#define ll long long
#define re register
#define in inline
ll a,b,t,tot=0;
ll mod=1e9+7;
ll dp[19][19][19]; 
in ll work(ll x,ll num){
	ll d[19];
	ll len=0,ans=0;
	while(x){
		d[++len]=x%10;
		x/=10;
	}
	for(int i=1;i<len;i++)
	for(int j=1;j<=9;j++)
	ans+=dp[i][j][num]%mod;
	
	for(int i=1;i<d[len];i++) ans=(ans+dp[len][i][num])%mod;
	
	for(int i=len-1;i>=1;i--){
		for(int j=0;j<d[i];j++)	ans=(ans+dp[i][j][num])%mod;
		for(int j=len;j>i;j--) 
		if(d[j]==num) ans=(ans+d[i]*pow(10,i-1)),ans%=mod; 
	}
	return ans%mod;
}
int main(){
	cin>>t;
    
	while(t--){
		tot=0;
		memset(dp,0,sizeof(dp));
		cin>>a>>b;
		for(re int i=0;i<=9;i++) dp[1][i][i]=1;
		for(re int i=2;i<=19;i++)
			for(re int j=0;j<=9;j++){
				for(re int k=0;k<=9;k++)
					for(re int l=0;l<=9;l++)
						dp[i][j][l]+=dp[i-1][k][l];
				dp[i][j][j]+=pow(10,i-1),dp[i][j][j]%=mod;
			}
		for(int i=1;i<=9;i++)
		(tot+=((((work(b+1,i)-work(a,i)+mod)%mod)*i)%mod+mod)%mod)%=mod;
		cout<<(tot+mod)%mod<<endl;
	}
	return 0;
}
2022/6/10 10:30
加载中...