传送门
题目大意：一个数被称为是平衡的数当且仅当对于所有出现过的数位，偶数出现奇数次，奇数出现偶数次。
给定 A ， B ，请统计出 [A,B] 内所有平衡的数的个数。
注意，这里的偶数是指出现过的数，并且不能计算前导零。
对于每一个数有三种状态：
0 ：这个数还木有出现过。
1 ：这个数出现过奇数次。
2 ：这个数出现过偶数次。
于是乎用一个三进制数来表示每一种状态。
3的10次方是59049，题目要求计算的数组最大为19位数，所以dp数组开成dp[20][60000]，第二维表示状态。
可能是oj时间限制得比较严，用scanf和printf会超时
具体解释请看代码：
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long LL;
LL dp[20][60000];
int bit[20];//保存数的每一位
bool check(int s)
{int num[10];for(int i = 0; i < 10; i++)//从低位到高位获取三进制状态的每一位{num[i] = s % 3;s /= 3;}for(int i = 0; i < 10; i++)if(num[i] != 0)//如果有不符合要求的，就直接返回0，该数不作为统计{if(i % 2 == 0 && num[i] == 2)return false;if(i % 2 == 1 && num[i] == 1)return false;}return true;//符合题目要求，则算一个
}
int getnews(int x, int s)
{int num[10];for(int i = 0; i < 10; i++){num[i] = s % 3;s /= 3;}if(num[x] == 0)num[x] = 1;elsenum[x] = 3 - num[x];int news = 0;for(int i = 9; i >= 0; i--){news *= 3;news += num[i];}return news;
}
LL dfs(int pos, int s, bool lim, bool z)//z用来判断是否一直是前导0
{if(pos == -1)//递归到了个位且枚举完成后，判断数是否符合要求return check(s);if(!lim && dp[pos][s] != -1)//如果没有达到上限且这个状态之前已经被记录过，直接返回return dp[pos][s];LL ans = 0;int End = lim ? bit[pos] : 9;for(int i = 0; i <= End; i++)//枚举下一位的每一位数ans += dfs(pos-1, (z&&i==0) ? 0 : getnews(i, s), lim && i == End, z&&i==0);//getnews是在确定下一位后获取新的状态的，如果一直是前导0，那么状态就是0if(!lim)dp[pos][s] = ans;return ans;
}
LL calc(LL n)
{int len = 0;while(n){bit[len++] = n % 10;n /= 10;}return dfs(len-1, 0, 1, 1);
}
int main()
{int T;LL l, r;memset(dp, -1, sizeof(dp));cin >> T;while(T--){cin >> l >> r;cout << calc(r) - calc(l-1) << endl;}return 0;
}