Time Limit:2000MS Memory Limit:32768KB 64bit IO Format:%lld & %llu
Description
A palindromic number or numeral palindrome is a 'symmetrical' number like 16461 that remains the same when its digits are reversed. In this problem you will be given two integers i j, you have to find the number of palindromic numbers between i and j (inclusive).
Input
Input starts with an integer T (≤ 200), denoting the number of test cases.
Each case starts with a line containing two integers i j (0 ≤ i, j ≤ 1017).
Output
For each case, print the case number and the total number of palindromic numbers between i and j (inclusive).
Sample Input
4
1 10
100 1
1 1000
1 10000
Sample Output
Case 1: 9
Case 2: 18
Case 3: 108
Case 4: 198
解题：回文数字。分成两种类型判断，一种是长度为奇数个的，一种是长度为偶数个的。
举个栗子。。。
20 是长度为2的，偶数长度，只要枚举dp[1][2]+d[1]什么意思呢？d[1]就是长度为1 的回文数字有多少个！dp[1][2]表示以1开始，长度为2的回文数字的个数。
再说120.。枚举d[2],由于是奇数，最后是遇到只有一个数字的情况，这是只要枚举最中间这一位就可以了，把低位与高位设置成一致的，1x1,只有从0开始枚举x，只要还在120的范围内，每枚举一个就加一，一旦不在120的范围内立即跳出循环。
再说一个偶数的长度1234.。。d[3]+dp[0][2]+dp[1][2],把低位跟高位一致后，1221，判断这个数是不是在1234内，是就加一，不是就加0，好吧加0就是不加，你赢了！！！！！！
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
#define LL long long
#define INF 0x3f3f3f
using namespace std;
LL dp[][],d[];
int len,bit[];
void init() {
int i,j;
for(i = ; i < ; i++)
dp[i][] = dp[i][] = ;
for(i = ; i < ; i++) {
for(j = ; j < ; j++) {
dp[j][i] = *dp[][i-];
}
}
d[] = ;//以0开始的。。。0就是
for(i = ; i < ; i++) {
for(j = ; j < ; j++)
d[i] += dp[j][i];
d[i] += d[i-];
}//算出0-长度为i的所有回文数字数目
}
LL go(int e) {
if(e < ) return ;
LL sum = ;
for(int i = ; i < ; i++) {
sum += dp[i][e];
}
return sum;
}
LL cal(LL n) {
if(n < ) return n+;
LL x = n,ans = ,y = ;
int i,j,k,v,u;
for(len = ; x; x /= , len++)
bit[len] = x%;
ans += d[len-];
for(j = ,v = len>>,i = len-; i >= v; i--,j++) {
if(i == len-) {
for(k = ; k < bit[i]; k++)
ans += dp[k][len];
} else if(i == j) {
u = i;break;
} else {
for(k = ; k < bit[i]; k++)
ans += dp[k][len-j*];
}
}
if(i == j) {//奇数个长度，最后结果受最中间的那位影响
for(i = ,j = len-; i < j; i++,j--)
bit[i] = bit[j];
for(k = ; k < ; k++){
bit[u] = k;
for(y = i = ; i < len; i++)
y = y*+bit[i];
if(y <= n) ans++;
else break;
}
}else{//偶数个长度，最后结果受最后一位影响
for(i = ,j = len-; i < j; i++,j--)
bit[i] = bit[j];
for(y = i = ; i < len; i++)
y = y*+bit[i];
if(y <= n) ans++;
}
return ans;
}
int main() {
init();
int t,ks = ;
LL a,b,c;
scanf("%d",&t);
while(t--){
scanf("%lld %lld",&a,&b);
if(a > b) swap(a,b);
printf("Case %d: %lld\n",ks++,cal(b)-cal(a-));
}
return ;
}