题目链接：http://www.spoj.com/problems/BALNUM/en/
题意：问你在[A,B]的闭区间内有几个满足要求的数，要求为每个出现的奇数个数为偶数个，每个出现的偶数个数为奇数个。
显然dfs很好想到dfs(int len , int even[] , int odd[] , int flag , int first)
even表示前len位出现偶数的总状态 ， odd表示前len位出现奇数的总状态，first表示是否为首位（特判全为0的结果）
但是这样写dfs dp不好搞，因为dp也要能表示前len位的奇偶出现状况，所以索性直接将dp的第二维保存为状态。
由于一共有0～9，10个数字，而且总共只有奇偶两种状态，所以直接用3进制来保存状态。
即dp[len][s],dfs(int len , int s , int flag , int first)
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef unsigned long long ull;
const int M = 6e4;
ull a , b , dp[20][M];
int dig[20];
int check(int x) {
int num[20];
for(int i = 0 ; i < 10 ; i++) {
num[i] = x % 3;
x /= 3;
}
for(int i = 0 ; i < 10 ; i++) {
if(num[i]) {
if(i % 2 == 0) {
if(num[i] == 2)
return 0;
}
else {
if(num[i] == 1)
return 0;
}
}
}
return 1;
}
int getsnew(int s , int x) {
int num[20];
for(int i = 0 ; i < 10 ; i++) {
num[i] = s % 3;
s /= 3;
}
if(num[x] != 0)
num[x] = 3 - num[x];
else
num[x] = 1;
int sum = 0;
int power = 1;
for(int i = 0 ; i < 10 ; i++) {
sum += num[i] * power;
power *= 3;
}
return sum;
}
ull dfs(int len , int s , int flag , int first) {
if(!len)
return check(s);
if(!flag && dp[len][s] != -1)
return dp[len][s];
int t = flag ? dig[len] : 9;
ull sum = 0;
for(int i = 0 ; i <= t ; i++) {
if(first) {
sum += dfs(len - 1 , i == 0 ? 0 : getsnew(s , i) , flag && i == t , first && i == 0);
}
else {
sum += dfs(len - 1 , getsnew(s , i) , flag && i == t , first && i == 0);
}
}
if(!flag)
dp[len][s] = sum;
return sum;
}
ull Gets(ull x) {
if(x == 0)
return 1;
int len = 0;
while(x) {
dig[++len] = x % 10;
x /= 10;
}
return dfs(len , 0 , 1 , 1);
}
int main() {
int t;
memset(dp , -1 , sizeof(dp));
scanf("%d" , &t);
while(t--) {
scanf("%lld%lld" , &a , &b);
printf("%lld
" , Gets(b) - Gets(a - 1));
}
return 0;
}