题解 P3413 【SAC#1 - 萌数】
简单的数位DP（传反参数活该WA爆）
回文串的题都不会做Emmm。
看到题目首先懵逼的，回文串？这怎么存啊？这么转移啊？
然后，脑回路清奇的我（这是正常的想法吧？？）就想到了是不是可以取补集，毕竟是数字。
一句话：正难则反
一个数如果前面包含了回文串，以后的状态也无法确定。
然后就想到了如何判断一个数完全不含回文串。
仔细思考一下，发现当一个数的任意一位都不和前两位的数字相同时，这个数就不含回文串。
手推了一下两个样例，发现好像没问题。
于是就打起来了。
设
和普通的数位DP一样转移。
code过程中主要有以下几个问题+细节：
1.
100%数据有1000位，这显然爆了。但是没事，这还方便了，不用拆数位了。直接字符串读入。（不要忘了翻转过来！！！！）
2.
都知道数位DP中最后求答案还用了前缀和的思想。如下：
那我们如何处理一个1000位的数字那？
对于
事实是：不用！！！！
可以直接求出
3.
由于取补集了吗，所以最后要拿
又要写高精了吗emmm？？？
当然不用，可以直接对
4.
转移时注意一下前导0，不要让前导0成为合法的pre或gpre（就是不要用当前位去匹配前面不存在的数）。
举个栗子：100以内，放到第三位，若第二位为空（此时第二位应赋为-1），第三位的0也是合法解。
5.
一定不要传反参数（调了我一早上QAQ）。
还有不要忘开
Think twice , code once.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
const long long mod=1e9+7;
const long long maxn=1001;
using namespace std;
string l,r;
long long len[maxn];
long long f[maxn][10][10];
long long dfs(long long pos,long long pre,long long gpre,bool lim,bool zero)
{
if(pos==0) return 1;
if(f[pos][pre][gpre]!=-1&&!lim&&!zero&&pre!=-1&&gpre!=-1) return f[pos][pre][gpre];
long long up=lim?len[pos]:9;
long long ans=0;
for(long long i=0;i<=up;i++)
{
if(i!=pre&&i!=gpre&&!zero)
ans=(ans+dfs(pos-1,i,pre,lim&&i==len[pos],0))%mod;
else if(zero)
ans=(ans+dfs(pos-1,(i==0&&zero)?-1:i,-1,lim&&i==len[pos],i==0&&zero))%mod;
}
if(!lim&&!zero&&pre!=-1&&gpre!=-1) return f[pos][pre][gpre]=ans;
return ans;
}
long long slove()
{
long long s=l.length();
for(long long i=0;i<s;i++)
len[s-i]=l[i]-'0';
long long ans1=dfs(s,-1,-1,1,1);
s=r.length();
for(long long i=0;i<s;i++)
len[s-i]=r[i]-'0';
long long ans2=dfs(s,-1,-1,1,1);
ans1--;
s=l.length();
for(long long i=2;i<=s;i++)
if(l[i]==l[i-1]||(l[i]==l[i-2]&&(i-2>=1)))
{
ans1++;
break;
}
return (ans2-ans1)%mod;
}
int main()
{
cin>>l>>r;
memset(f,-1,sizeof f);
long long numl=0,numr=0;
long long s1=l.length(),s2=r.length();
for(long long i=0;i<s1;i++)
numl=(numl*10%mod+(l[i]^48))%mod;
for(long long i=0;i<s2;i++)
numr=(numr*10%mod+(r[i]^48))%mod;
printf("%lld",((numr-numl-slove()+1)%mod+mod)%mod);
return 0;
}