真毒瘤。。
这个题目真的耗了我半小时！其实现在想起来还好，思路应该不难想，这里提供一种思路，一开始看这题想着不好判断回文，既然回文不好判断，那就判断不回文呗，正难则反嘛~~~我们要知道，对于一个不是回文串的串，每个字符与前面一个字符和前面第二个字符不相同，因此我们记录两个值$last1,last2$表示上一位的值以及上两位的值，剩下的就是数位$dp$啦~~~
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define int long long
#define ll long long
#define N 1010
#define mod 1000000007
using namespace std;
int val[N];
char l[N],r[N];
int f[N][21][21];
ll lenl,lenr;
ll Dfs(int pos,int last2,int last1,bool limit,bool lead)
{
if(!pos)
return 1;
if(!limit&&!lead&&f[pos][last2][last1]!=-1)
return f[pos][last2][last1]%mod;
int maxn=limit?val[pos]:9;
ll ans=0;
for(int i=0;i<=maxn;++i)
{
if(lead&&!i)
ans=(ans+Dfs(pos-1,-1,-1,limit&&(i==maxn),1)%mod)%mod;
else
if(i!=last1&&i!=last2)
ans=(ans+Dfs(pos-1,last1,i,limit&&(i==maxn),0)%mod)%mod;
}
if(!limit&&!lead)
f[pos][last2][last1]=ans%mod;
return ans%mod;
}
ll Get()
{
for(int i=0;i<lenl;++i)
val[lenl-i]=l[i]-'0';
ll numl=Dfs(lenl,-1,-1,1,1)%mod;
--numl;
for(int i=0;i<lenr;++i)
val[lenr-i]=r[i]-'0';
ll numr=Dfs(lenr,-1,-1,1,1)%mod;
for(int i=2;i<lenl;++i)
if(l[i]==l[i-1]||l[i]==l[i-2])
{
++numl;
break;
}
return (numr-numl)%mod;
}
signed main()
{
cin>>l>>r;
lenl=strlen(l),lenr=strlen(r);
memset(f,-1,sizeof(f));
ll nl=0,nr=0;
for(int i=0;i<lenl;++i)
nl=((nl*10)+l[i]-'0')%mod;
// cout<<"
nl:"<<nl<<"
";
for(int i=0;i<lenr;++i)
nr=((nr*10)+r[i]-'0')%mod;
// cout<<"
nr:"<<nr<<"
";
printf("%lld",((nr-nl+1-Get())%mod+mod)%mod);
return 0;
}