文件详细信息

下载本文件

本文件的大小为 974 字节。

#include<cstdio>
#include<cstring>
typedef long long ll;
const int maxn=1005;
const ll P=1000000007;
char l[maxn],r[maxn],*num;
int nl,nr,len;
ll f[maxn][11][11][11][2];
ll dfs(int digit,int num1,int num2,int num3,int ok,int limit,int zero){
	if(digit==len+1)return ok;
	if(!limit&&!zero&&f[digit][num1][num2][num3][ok]!=-1)return f[digit][num1][num2][num3][ok];
	ll ans=0;
	int d=limit?num[digit]-'0':9;
	for(int i=0;i<=d;i++)ans+=dfs(digit+1,num2,num3,i?i:zero?10:0,ok||i==num2||i==num3,limit&&i==d,zero&&i==0);
	ans%=P;
	if(!limit&&!zero)f[digit][num1][num2][num3][ok]=ans;
	return ans;
}
ll solve(char*s,int n){
	num=s,len=n;
	memset(f,-1,sizeof(f));
	return dfs(1,10,10,10,0,1,1);
}
int judge(char*s,int n){
	if(s[1]==s[2])return 1;
	for(int i=3;i<=n;i++)
		if(s[i]==s[i-2]||s[i]==s[i-1])
			return 1;
	return 0;
}
int main(){
	scanf("%s%s",l+1,r+1);
	nl=strlen(l+1),nr=strlen(r+1);
	ll ans=(solve(r,nr)-solve(l,nl)+judge(l,nl)+P)%P;
	printf("%lld\n",ans);
	return 0;
}