1 #include 2 #include 3 #include 4 #include
5 #include 6 #include 7 #define g() getchar()
8 #define rg register
9 #define go(i,a,b) for(rg int i=a;i10 #define back(i,a,b) for(rg int i=a;i>=b;i--)
11 #define db double
12 #define ll long long
13 #define il inline
14 #define pf printf
15 #define mem(a,b) memset(a,b,sizeof(a))
16 using namespace std;
17 ll fr(){
18 ll w=0,q=1;
19 char ch=g();
20 while(ch‘0‘||ch>‘9‘){
21 if(ch==‘-‘) q=-1;
22 ch=g();
23 }
24 while(ch>=‘0‘&&ch‘9‘) w=(w1)+(w3)+ch-‘0‘,ch=g();
25 return w*q;
26 }
27 ll A,B;
28 int a[15],f[15][10];
29 il int solve(rg int l,rg int lst,bool lim){
30 if(!l) return 1;//如果已经到了最后一位,那么方案数为1
31 if(lst>0&&lim==0&&f[l][lst]!=-1) return f[l][lst];
32 //记忆化,f数组记录的是没有限制的情况下的方案数
33 rg int up=lim?a[l]:9,ans=0,nxt;//up记录上限
34 go(i,0,up){
35 if(abs(lst-i)2) continue;
36 nxt=i;
37 if(lst==-2&&nxt==0) nxt=-2;
38 ans+=solve(l-1,nxt,lim&&nxt==a[l]);
39 }
40 if(!lim&&lst>0) f[l][lst]=ans;//记录一下答案
41 return ans;
42 }
43 il int work(ll x){
44 rg int len=0;
45 while(x) a[++len]=x%10,x/=10;
46 return solve(len,-2,1);//因为数字是倒序记录的,所以倒序搜索
47 }
48 int main(){
49 //freopen("","r",stdin);
50 //freopen("","w",stdout);
51 A=fr();B=fr();
52 mem(f,-1);
53 pf("%d\n",work(B)-work(A-1));
54 return 0;
55 }
