BALNUM - Balanced Numbers
Balanced numbers have been used by mathematicians for centuries. A positive integer is considered a balanced number if:
1) Every even digit appears an odd number of times in its decimal representation
2) Every odd digit appears an even number 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 both A 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
Example
Input:
2
1 1000
1 9
Output:【题解】
147
4
经典好题，很考究思维，我也是参考了大神博客才想明白的。
做法很妙，下面来说一说。
要求一个区间内满足下面条件的数的个数：
每一个奇数出现偶数次，并且每一个偶数出现奇数次；
第一次直接用两个状态来表示奇数和偶数出现的次数，后来发现题意理解错了；
要表示每个数字出现的次数，有10个状态，怎么表示呢？很显然，用状压最适合不过了。
用个3进制状态，表示每一位上数字出现的次数，0表示没出现过，1表示出现奇数次，2表示出现偶数次，这样0~9 一共10个状态就被表示了，而3^10<60000，很小。
剩下的部分见代码注释：
【AC代码】
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=25;
ll dp[N][60000];//第一维表示位数 第二维是三进制表示的每个数字出现的次数
ll m,n;
int num[N];
bool gg(int x)//是不是满足条件的数
{
int s[10];
for(int i=0;i<10;++i)//得到三进制数的每一位，s[i]表示数字i出现了i次
{
s[i]=x%3;
x/=3;
}
for(int i=0;i<10;++i)
{
if(s[i]!=0)//如果i出现过
{
if(s[i]==1&&i%2==1)//i是奇数并且出现了奇数次 不符合题意
return 0;
if(s[i]==2&&i%2==0)//i是偶数并且出现了偶数次 不符合题意
return 0;
}
}
return 1;
}
int get_num(int ii,int x)//把ii的加进去
{
int s[10];
for(int i=0;i<10;++i)//同上
{
s[i]=x%3;
x/=3;
}
//再啰嗦一遍 s[i]表示i出现的次数
if(s[ii]==0)//如果这个数ii还没出现过 就把s[ii]置为1 表示出现了一次
s[ii]=1;
else //如果已经出现过 出现了奇数次的话就3-s[ii]变为偶数次，如果出现了偶数次的话就3-s[ii]变为奇数次
s[ii]=3-s[ii];
int ans=0;
for(int i=9;i>=0;--i)//得到新的表示状态的数 一定要高位开始 可能三进制数不够10位 高位可能为0
{
ans*=3;
ans+=s[i];
}
return ans;
}
ll dfs(int pos,int value,int zero,int limit)//往下都是模板了
{
if(pos<0) return gg(value);
if(!limit && dp[pos][value]!=-1) return dp[pos][value];
ll ans=0;
int endi = limit ? num[pos] : 9 ;
for(int i=0;i<=endi;++i)
{
ans+=dfs(pos-1,(zero&&i==0)?0:get_num(i,value),zero&&(i==0),limit && i==endi );
}
if(!limit) dp[pos][value]=ans;
return ans;
}
ll solve(ll x)
{
int len=0;
while(x)
{
num[len++]=x%10;
x/=10;
}
return dfs(len-1,0,1,1);
}
int main()
{
int t;
memset(dp,-1,sizeof dp);
scanf("%d",&t);
while(t--)
{
scanf("%lld%lld",&m,&n);
printf("%lld\n",solve(n)-solve(m-1));
}
}