洛谷3413 萌数
数位dp。
因为我们知道如果有回文子串，一定有一个回文的中心。我们只要能找到一个满足长度$geq 2$的回文中心就可以了。
也就是说找到一个满足$a[i]=a[i+1]$或$a[i]=a[i+2]$的地方就是萌数了。
但是还需要注意前导0的特殊处理、记忆化搜索的状态里面负数的处理（有-1的情况可以所有情况+1存储）。
//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=2000+10;
const long long mod=1e9+7;
string l,r;
int len1,len2,a[2][maxn];
long long ans,dp[maxn][12][12][2];
long long f(bool p,int pos,int x,int y,int now) {//4:lim 2:fir 1:cute
if(!pos) return now&1;
if(!(now&4)&&dp[pos][x+1][y+1][now&1]!=-1) return dp[pos][x+1][y+1][now&1];
int g=(now&4)? a[p][pos]:9;long long rs=0;
for(int i=0;i<=g;++i)
(rs+=f(p,pos-1,(now&2)&&(!i)? -1:i,x,(now|(i==x||i==y))&(((!i)<<1)|(g==i)<<2|1)))%=mod;
if(!(now&4)) dp[pos][x+1][y+1][now&1]=rs;
return rs;
}
int main() {
cin>>l>>r;
len1=l.length();len2=r.length();
for(int i=0;i<len1;++i) a[0][len1-i]=l[i]-'0';
for(int i=0;i<len2;++i) a[1][len2-i]=r[i]-'0';
memset(dp,-1,sizeof(dp));ans=f(1,len2,-1,-1,6);
ans=(ans-f(0,len1,-1,-1,6)+mod)%mod;
a[0][len1+1]=-1;
for(int i=len1-1;i>=1;--i) if(a[0][i]==a[0][i+1]||a[0][i]==a[0][i+2]) {
(ans+=1)%=mod; break;
}
printf("%lld",ans);
return 0;
}