10分求条
查看原帖
10分求条
983555
fengzhaoyu楼主2024/12/3 22:08
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int dp[1001][20][20][2];
int a[2100];
int dfs(int now,int limit,int p1,int p2,bool is_0,bool st,bool las_0)
{
	int ans=0;
	if(now<0)
	{
		if(st==1) return 1;
		return 0;
	}
	if(is_0 && !limit && ~dp[now][p1][p2][st]) return dp[now][p1][p2][st]%mod;
	int up=limit?a[now]:9;
	for(int i=0;i<=up;i++)
	{
		int sst=st;
		if(i==p1 && is_0) sst=1;
		if(i==p2 && las_0) sst=1;
		ans=(ans+dfs(now-1,limit&&(i==up),i,p1,is_0||i,sst,is_0))%mod;
		ans%=mod;
	}
	if(is_0 && !limit) dp[now][p1][p2][st]=ans;
	return ans%mod;
}
signed main()
{
	int cnt=0;                   
	string l,r;
	cin>>l>>r;
	cnt=l.size();
	for(int i=0;i<cnt;i++)
	{
		a[i]=l[cnt-i-1]-'0';
	}
	for(int i=0;i<cnt;i++) 
	{
		if(a[i]!=0)
		{
			a[i]-=1;
			break;
		}
		else if(a[i]==0)
		{
			a[i]=9;
		}          
	}
	cnt=l.size();
	memset(dp,-1,sizeof dp); 
	int ans1=dfs(cnt-1,1,0,0,0,0,0);
	cnt=0;
	memset(dp,-1,sizeof dp);
	memset(a,0,sizeof a);
	cnt=r.size();
	for(int i=0;i<cnt;i++)
	{
		a[i]=r[cnt-i-1]-'0';
	}
	int ans2=dfs(cnt-1,1,0,0,0,0,0);
	cout<<(ans2-ans1+mod)%mod<<endl;
	return 0;
}
2024/12/3 22:08
加载中...