原题传送门 P2657。

本人刚学完数位 DP，写篇题解巩固一下。数位 DP 相当于一种拆数游戏，但需要满足一些条件。
通常若求 $[l,r]$ 内满足条件的个数，可拆为 $[1,r]$ 内满足条件的个数减去 $[1,l-1]$ 内满足条件的个数。

这题和原题的唯一区别就是数据范围 $1 \le a \le b\le 10^{18}$，当然了记忆化搜索肯定是能过的。

进入正题，递归函数可为 $dfs_{pos,lim,last,z}$，其中 $pos$ 表示从左往右的第几位，$lim$ 表示是否顶到了上界，$last$ 表示上一位上的数字， $z$ 表示是否有前导零。
比如数 $13085$：

$$$ \begin{array}{c} pos=2,last=1,z=0,lim=1 \end{array} $$$

转移方程如下：

$$$ dfs_{pos,lim,last,z}=\sum_{|i-last| \ge 2}^{n} dfs_{pos+1,lim \wedge i=n,z \wedge (i=0)?-2:i,z \wedge (i=0)?1:0} $$$

其中 $a?b:c$ 为 C++ 中的条件运算符。
对于上式，若 $z\wedge (i=0)$，则仍有前导零，并且下一位数字可以随便取，将 $last \gets -2$ 就能保证下一位数字可以任取。

代码如下：

#include<bits/stdc++.h>
#define debug cout<<"here"
#define int long long
using namespace std;
const int N=20;
int f[N][N],l,r,len,a[N];//f[pos][last]
int dfs(int pos,bool lim,int last,bool z){
	if(pos>len){
		return 1;
	}
	if(!lim&&f[pos][last]!=-1){
		return f[pos][last];
	}
	int n=lim?a[len-pos+1]:9;
	int res=0;
	for(int i=0;i<=n;i++){
		if(abs(i-last)<2){
			continue;
		}
		if(z&&i==0){
			res+=dfs(pos+1,lim&&i==n,-2,1);
		}
		else{
			res+=dfs(pos+1,lim&&i==n,i,0);
		}
	}
	if(!z&&!lim){
		f[pos][last]=res;
	}
	return res;
}
int sol(int n){
	len=0;
	while(n){
		a[++len]=n%10;
		n/=10;
	}
	memset(f,-1,sizeof f);
	return dfs(1,1,-2,1);
}
signed main(){
	cin>>l>>r;
	cout<<sol(r)-sol(l-1);
	return 0;
}