Description
Victor 是一名热爱数字的同学。他最近在思考这样一个问题：
一个字符串是回文的当且仅当它倒过来还和原来相同。那么如果一个数的数串没有一个长度超过1 的子串是回文串的话，它就是palindrome-free 的。例如：16276 是palindrome-free的，而17276 不是，因为它包含了回文串727。
Victor 想知道在a 到b 的区间内，有多少个数是palindrome-free 的。
Input
从文件numbers.in 中读入数据。
包括两个数字a,b。
Output
输出到文件numbers.out 中。
输出包含一个整数：区间a,…,b 中palindrome-free 的数的总个数(包括a,b)。
Sample Input
输入1：
123 321
输入2：
123456789 987654321
Sample Output
输出1：
153
输出2：
167386971
Data Constraint
对于16% 的数据，b - a <= 200。
对于24% 的数据，b - a <= 10^5。
对于32% 的数据，b - a <= 10^6。
对于100% 的数据，0 <= a <= b <= 10^18
Solution
这道题是一道典型的数位DP，即根据枚举数位来统计结果的动态规划。
套路设
Work(x) 表示从0 到x 的答案，则答案即为Work(b)−Work(a−1) 。因为回文只需判断长度为
2 或3 的中心串即可，于是设出状态
F[i][j][k][l] 表示填了i 位、 上两位为j 、l 限制越界0/1 的方案数。为方便转移，
k 为0 （第1 到i 为前导0 ）、1 （第1 到i−1 为前导0 ） 或2 （其他情况）。答案即为
∑F[n][i][j][k] 。
Code
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long n,m;
int a[20];
long long f[20][100][3][2];
inline long long work(long long x)
{
for(a[0]=0;x;x/=10) a[++a[0]]=x%10;
reverse(a+1,a+1+a[0]);
memset(f,0,sizeof(f));
f[0][0][0][1]=1;
for(int i=0;i<a[0];i++)
for(int j=0;j<=99;j++)
for(int k=0;k<2;k++)
if(k)
{
for(int l=0;l<a[i+1];l++)
{
if(!l) f[i+1][j%10*10+l][0][0]+=f[i][j][0][1]; else
f[i+1][j%10*10+l][1][0]+=f[i][j][0][1];
if(j<=9 && j && j!=l) f[i+1][j%10*10+l][2][0]+=f[i][j][1][1];
if(j%10!=l && j/10!=l) f[i+1][j%10*10+l][2][0]+=f[i][j][2][1];
}
if(!a[i+1]) f[i+1][j%10*10+a[i+1]][0][1]+=f[i][j][0][1]; else
f[i+1][j%10*10+a[i+1]][1][1]+=f[i][j][0][1];
if(j<=9 && j && j!=a[i+1]) f[i+1][j%10*10+a[i+1]][2][1]+=f[i][j][1][1];
if(j%10!=a[i+1] && j/10!=a[i+1]) f[i+1][j%10*10+a[i+1]][2][1]+=f[i][j][2][1];
}else
for(int l=0;l<=9;l++)
{
if(!l) f[i+1][j%10*10+l][0][0]+=f[i][j][0][0]; else
f[i+1][j%10*10+l][1][0]+=f[i][j][0][0];
if(j<=9 && j && j!=l) f[i+1][j%10*10+l][2][0]+=f[i][j][1][0];
if(j%10!=l && j/10!=l) f[i+1][j%10*10+l][2][0]+=f[i][j][2][0];
}
long long sum=0;
for(int i=0;i<=99;i++)
for(int j=0;j<3;j++)
for(int k=0;k<2;k++)
sum+=f[a[0]][i][j][k];
return sum;
}
int main()
{
scanf("%lld%lld",&n,&m);
printf("%lld",work(m)-work(n-1));
return 0;
}