数位DP10pts求调
查看原帖
数位DP10pts求调
764574
hmy0213楼主2024/10/10 19:17
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const ll P=1e9+7;
string l,r;
ll len,dp[1005][15][15][4],n;
ll dfs(string s,int pos,int pre2,int pre1,int limit){
	if(pos==len) return 1;
	if(dp[pos][pre2][pre1][limit]!=-1) return dp[pos][pre2][pre1][limit];
	ll ans=0;
	if(pre1==10){
		ans=(ans+dfs(s,pos+1,10,10,0)%P);
		for(int i=1;i<=(limit?s[pos]-'0':9);i++){
			ans=(ans+dfs(s,pos+1,pre1,i,(limit&&i==s[pos]-'0'))%P);
		}
	}
	else{
		for(int i=limit;i<=(limit?s[pos]-'0':9);i++){
			if(pre1!=i&&i!=pre2) ans=(ans+dfs(s,pos+1,pre1,i,(limit&&i==s[pos]-'0'))%P);
		}
	}
	return dp[pos][pre2][pre1][limit]=ans;
}
ll slove(string s){
	if(s[0]=='0') return 0;
	len=s.size();
	n=0;
	for(int i=len-1,j=1;i>=0;i--,j=(j*10%P)){
		n=(n+(s[i]-'0')*j)%P;
	}
	for(int i=0;i<len;i++){
		for(int j=0;j<=10;j++){
			for(int k=0;k<=10;k++){
				for(int f=0;f<=1;f++){
					dp[i][j][k][f]=-1;
				}
			} 
		}
	}
	return (n-dfs(s,0,10,10,1)+P)%P;
}
ll check(string s){
	for(int i=1;i<s.size();i++){
		if(s[i-1]==s[i]) return 1;
		if(i>=2&&s[i-2]==s[i]) return 1;
	}
	return 0;
}
int main(){
	cin>>l>>r;
	cout<<(slove(r)-slove(l)+check(l)+P)%P;
	return 0;
}
2024/10/10 19:17
加载中...