#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#define ll long long
#define MD 1000000007
using namespace std;
int s1[1005],s2[1005];
int st[1005];
ll f[1005][15][15][2][2][2];
//pos 最大有1000位所以开到1000+
string sx,sy;
int len;
// pre2 当前位置的第前两位 pre1 当前位置的第前一位
// lead 前导零 我设置的数是15
// pos 当前位置
// limit 最高为限制
// flag 如果flag为1 则当前这个数是萌的 否则它为0
// len 记录当前字符串的长度
ll dfs (int pre2,int pre1,int pos,int limit,int lead,int flag)
{
if(pos>len)
return flag;
ll ret=0;
if(f[pos][pre1][pre2][limit][lead][flag]!=-1)
return f[pos][pre1][pre2][limit][lead][flag]%MD;
int top=limit?st[pos]:9;
for(int i=0; i<=top; i++)
{
//如果这个数是萌的 无需再判断了
if(flag&&pre1!=-2)
ret=(ret%MD+dfs(pre1,(lead&&i==0)?-2:i,pos+1,limit&&i==top,(lead&&i==0)?1:0,1)%MD)%MD;
else
{
//不知道这个数萌不萌
//关键:如果aa或aba那么就合法
if(pre1==i&&pre1!=-2||pre2==i&&pre2!=-2&&pre1!=-2)
ret=(ret%MD+dfs(pre1,(lead&&i==0)?-2:i,pos+1,limit&&i==top,(lead&&i==0)?1:0,1)%MD)%MD;//1
else
ret=(ret%MD+dfs(pre1,(lead&&i==0)?-2:i,pos+1,limit&&i==top,(lead&&i==0)?1:0,0)%MD)%MD;//0
}
//写法有很多种 我的代码比较啰嗦
}
f[pos][pre1][pre2][limit][lead][flag]=(ret%MD);
//记忆化搜索直接把所有状态存上
//这样存不容易出错
return ret%MD;
}
ll work (int le,int ok)
{
memset(st,0,sizeof(st));
memset(f,-1,sizeof(f));
len=le;
if(ok==1)
{
for(int i=1; i<=len; i++)
st[i]=s2[i];
}
else
{
for(int i=1; i<=len; i++)
st[i]=s1[i];
}
return dfs(-2,-2,1,1,1,0)%MD;
}
int main()
{
// 一定要读入字符串(读入的数有一千位啊)
cin>>sx>>sy;
int len1=sx.length();
for(int i=0; i<len1; i++)
{
s1[i+1]=sx[i]-‘0‘;
}
int len2=sy.length();
for(int i=0; i<len2; i++)
{
s2[i+1]=sy[i]-‘0‘;
}
s1[len1]--;
ll ans1=work(len1,0);
ll ans2=work(len2,1);
printf("%lld",((ans2-ans1)%MD+MD)%MD);
//这里一定要模不然会输出负数
return 0;
}
luogu P3413 SAC#1 - 萌数 数位dp