SPOJ Problem Set (classical)10606. Balanced NumbersProblem code: BALNUM
Balanced numbers have been used by mathematicians for centuries. A positive integer is considered a balanced number if:
1) Everyevendigit appears anoddnumber of times in its decimal representation
2) Everyodddigit appears anevennumber of times in its decimal representation
For example, 77, 211, 6222 and 112334445555677 are balanced numbers while 351, 21, and 662 are not.
Given an interval [A, B], your task is to find the amount of balanced numbers in [A, B] where bothA and B are included.
Input
The first line contains an integer T representing the number of test cases.
A test case consists of two numbers A and B separated by a single space representing the interval. You may assume that 1 <= A <= B <= 1019
Output
For each test case, you need to write a number in a single line: the amount of balanced numbers in the corresponding interval
ExampleInput:21 10001 9Output:1474
/**spoj10606 数位dp （求出现的数字，，所有偶数出现奇数次，所有奇数出现偶数次）解题思路：3进制表示数字0~9的出现情况，0表示没有出现，1表示奇数次，2表示偶数次*/#include <string.h>#include <stdio.h>#include <iostream>#include <algorithm>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){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,int flag,int z){if(pos==-1)return check(s);if(!flag&&dp[pos][s]!=-1)return dp[pos][s];LL ans=0;int end=flag?bit[pos]:9;for(int i=0;i<=end;i++){ans+=dfs(pos-1,(z&&i==0)?0:getnews(i,s),flag&&i==end,z&&i==0);}if(!flag)dp[pos][s]=ans;return ans;}LL solve(LL n){int len=0;while(n){bit[len++]=n%10;n/=10;}return dfs(len-1,0,1,1);}int main(){int T;memset(dp,-1,sizeof(dp));LL a,b;scanf("%d",&T);while(T–){scanf("%lld%lld",&a,&b);printf("%lld\n",solve(b)-solve(a-1));}return 0;}
却还是，会愚蠢的选择相互敌视的方式。即使背脊相抵，
