数位 dp。

思路

首先如果一个串包含一个回文串，那么必定会包含一个长度为 $2$ 或 $3$ 的回文串。

我们可以转化为求有多少数不包含长度为 $2$ 或 $3$ 的回文串。此时只需要记录一下前一位，前两位的数 $last_1,last_2$，我们在转移时枚举第 $i$ 位选择的数 $j$ 时只需要判断 $j\not=last_1,last_2$ 即可。

于是就做完啦！

嗯其实没有，主要问题是恶心很多数位 dp 问题的前导零。这里，前导零并不造成回文串。所以我们还得枚举最高位，限制最高位不能放 $0$。

等下，不会真有人枚举最高位是 $1\sim 9$ 了吧。考虑到我们要做的只是限制不为 $0$，而我们刚才说了，要求新的一位不是 $last_1$ 或 $last_2$，那么我们 dfs 的时候只需要设 $last_2=0$ 即可。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int f[21][11][11];
int a[21],n;
int dfs(int now,int lst1,int lst2,int tp){
	if(now==0){
		return 1;
	}
	if(!tp&&f[now][lst1][lst2]!=-1){
		return f[now][lst1][lst2];
	}
	if(tp){
		int ans=0;
		for(int i=0;i<a[now];i++){
			if(i!=lst1&&i!=lst2){
				ans+=dfs(now-1,lst2,i,0);
			}
		}
		if(a[now]!=lst1&&a[now]!=lst2) ans+=dfs(now-1,lst2,a[now],1);
		return ans;
	}
	else{
		f[now][lst1][lst2]=0;
		for(int i=0;i<10;i++){
			if(i!=lst1&&i!=lst2){
				f[now][lst1][lst2]+=dfs(now-1,lst2,i,0);
			}
		}
		return f[now][lst1][lst2];
	}
}
int count(int s){
	if(!s) return 0;
	if(s<10) return s;
	n=0;
	while(s){
		a[++n]=s%10;
		s/=10;
	}
	int ans=dfs(n,0,10,1);
	for(int i=n-1;i>=1;i--){
		ans+=dfs(i,0,10,0);
	}
	return ans;
}
signed main(){
	int a,b;
	cin>>a>>b;
	memset(f,-1,sizeof(f));
	cout<<count(b)-count(a-1);
	return 0;
}