题目描述：
求给定区间中的回文数有多少个？
首先明确一点，如果一个数是回文数，那么给这个数两边加上相同的数，那么这个数还是回文数。
根据这点就可以进行递推了，p[start][end]=9*p[start+1][end-1](start位不为0)+p[start-1][end](start位为0)；
在设计dfs的时候，由于回文数是对称的，所以只需要一个变量cur(cur>mid)就可以表示从cur到cur对称的位置的回文数的个数；
d[start][cur]表示从start位到cur位时,回文数的个数。
这句话隐含的意思是最高位为start，枚举到第cur位，由于是回文数，所以当cur>mid时，[cur,start]位确定，他们的对称位[1,start+1-cur]也就确定了，
还需枚举[cur,mid]这些位；当cur=mid时任意枚举，对回文数没有影响，当cur<mid时，由于是回文数，已经确定了，不需枚举。
再增加一维表示当前枚举的数字是不是回文数(([start,cur]位是否为回文数);
d[start][cur][state]表示从start位到cur位时,状态为state时回文数的个数。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define LL long long
LL n,m;
LL d[][][];
int digit[];
int num[];
LL dfs(int start,int cur,int Zero,int state,bool fp)
{
if(!cur)
return state;
if(!fp && d[start][cur][state]!= -)
return d[start][cur][state];
LL ret = ;int fpmax = fp ? digit[cur] : ;
for(int i=;i<=fpmax;i++)
{
if( (Zero &&(i==)) )
ret+=dfs(start-,cur-,Zero&&(i==),state, fp&& i==fpmax);
else
{
num[cur]=i;
if( (start & )== )
{
int mid=((start+)>>);
if(cur== mid)
{
ret+=dfs(start,cur-,,state,fp&& i==fpmax);
}
else if(cur < mid )
{
ret+=dfs(start,cur-,,state&& (num[mid*-cur]==i),fp&& i==fpmax);
}
else if(cur>mid)
{
ret+=dfs(start,cur-,,state,fp&& i==fpmax);
}
}
else
{
int mid=(start>>)+;
if(cur<mid)
{
ret+=dfs(start,cur-,,state&& (num[start+-cur]==i),fp&& i==fpmax);
}
else
{
ret+=dfs(start,cur-,,state,fp&& i==fpmax);
}
}
}
}
if(!fp) //如果是前缀，当前得到的ret的值，就不能代表dp[len][state]的值
d[start][cur][state] = ret;
return ret;
} LL f(LL n)
{
int len = ;
if(n==-)
return ;
while(n)
{
digit[++len] = n % ;
n /= ;
}
LL answer=dfs(len,len,,,true);
return answer;
}
void init()
{
memset(d,-,sizeof(d));
}
int main()
{
// freopen("test.txt","r",stdin);
int t;
scanf("%d",&t);
int Case=;
while(t--)
{
scanf("%lld%lld",&n,&m);
init();
if(n>m)
swap(n,m);
printf("Case %d: %lld\n",++Case,f(m)-f(n-));
}
return ;
}