先打出暴搜代码，参数有\(pos,limit,hui\)，其中bool类型的\(hui\)表示到当前是否有回文。
暴搜代码中加入了一个剪枝：if(!limit&&hui) return pow10[pos];，这个!limit很重要，我就是因为这个没加，暴搜代码都调了半天。然后就是if(pos==0) return hui;。
我们还需要记录下填过的位是不是前导\(0\)，所以用-1表示前导\(0\)。
接下来考虑怎么记忆化，我们发现，当前的答案只和\(pos\)、\(sta[pos+1]\)和\(sta[pos+2]\)有关。我们在\(pos\)相同的情况下分类讨论：
- 后\(2\)位都不是前导\(0\)，而且都不一样。
- 后\(2\)位都不是前导\(0\)，而且都一样。
- 后\(2\)位中最高位是前导\(0\)。
- 后\(2\)位中都是前导\(0\)。
我们又可以发现，第\(2\)种情况和第\(3\)中情况本质上是一样的。所以\(pos\)相同的时候，一共只有\(3\)中情况，我们根据情况计算出状态码，然后用\(f[pos][stanum]\)来记忆化。空间和时间都很优，\(1010*3\)。
注意
- \(L,R\)足足有\(1000\)位，所以得用
string存。而字符串减\(1\)操作不好弄，所以答案用\(solve(r)-solve(l)\)，然后特判\(l\)是否符合条件，符合条件再额外加\(1\)。 - 虽然不需要开
long long，但是打表计算\(pos10\)的时候需要类型转换一下再取模，否则\(*10\)会溢出。
Code
点击查看代码
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
string l,r;
int a[1010],sta[1010],len;
int f[1010][3],pow10[1010];
int dfs(int pos,bool limit,bool hui){
if(!limit&&hui) return pow10[pos];
if(pos==0) return hui;
int stanum;
if(sta[pos+1]==-1&&sta[pos+2]==-1) stanum=2;
else if(sta[pos+2]==-1||sta[pos+1]==sta[pos+2]) stanum=1;
else stanum=0;
if(!limit&&f[pos][stanum]!=-1) return f[pos][stanum];
int rig=limit?a[pos]:9,ans=0;
for(int i=0;i<=rig;i++){
bool is=(sta[pos+1]==-1&&i==0);
sta[pos]=is?-1:i;
bool thui=hui||(sta[pos]==sta[pos+1]&&sta[pos+1]!=-1)||(sta[pos]==sta[pos+2]&&sta[pos+2]!=-1);
ans=(ans+dfs(pos-1,limit&&i==rig,thui))%mod;
}
if(!limit) f[pos][stanum]=ans;
return ans;
}
int solve(string s){
len=s.size();
for(int i=0;i<len;i++){
a[len-i]=s[i]-'0';
}
sta[len+1]=sta[len+2]=-1;
return dfs(len,1,0);
}
int main(){
pow10[0]=1;
for(int i=1;i<=1005;i++) pow10[i]=(10ll*pow10[i-1])%mod;
memset(f,-1,sizeof f);
cin>>l>>r;
bool is=0;
int len=l.size();
for(int i=0;i<len-2;i++){
if(l[i]==l[i+1]||l[i]==l[i+2]){
is=1;
break;
}
}
if(l[len-2]==l[len-1]) is=1;
cout<<(solve(r)-solve(l)+is+mod)%mod;
return 0;
}