BALNUM - Balanced Numbers
no tags
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 题意：l,r之间多少满足条件的数：每一个奇数出现偶数次，每一个偶数出现奇数次。 也就是说 1 3 5 7 9 都只能出现偶数次 0 2 4 6 8 10都只能出现奇数次 注意去除前导0 思路：用一个三进制数组统计0-9出现的奇偶次 0代表没出现 1代表出现奇数次 2代表出现偶数次，记忆化时把该数组转化成一个十进制数s保存，用到了三进制和十进制互转。 #include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <string>
#include <stack>
using namespace std;
typedef long long ll;
#define PI 3.1415926535897932
#define E 2.718281828459045
#define INF 0x3f3f3f3f
#define mod 100000007
const int M=1005;
int n,m;
int cnt;
int sx,sy,sz;
int mp[1000][1000];
int pa[M*10],rankk[M];
int head[M*6],vis[M*100];
int dis[M*100];
ll prime[M*1000];
bool isprime[M*1000];
int lowcost[M],closet[M];
char st1[5050],st2[5050];
int len[M*6];
typedef pair<int ,int> ac;
//vector<int> g[M*10];
ll dp[50][60000]; //没想到坑在数组开小了，越界竟然还能运行？
int has[10500];
int month[13]= {0,31,59,90,120,151,181,212,243,273,304,334,0};
int dir[8][2]= {{0,1},{0,-1},{-1,0},{1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
void getpri()
{
ll i;
int j;
cnt=0;
memset(isprime,false,sizeof(isprime));
for(i=2; i<1000000LL; i++)
{
if(!isprime[i])prime[cnt++]=i;
for(j=0; j<cnt&&prime[j]*i<1000000LL; j++)
{
isprime[i*prime[j]]=1;
if(i%prime[j]==0)break;
}
}
}
struct node
{
int v,w;
node(int vv,int ww)
{
v=vv;
w=ww;
}
};
vector<int> g[M*100];
string str[1000];
int bit[15];
bool check(int s){
int i;int dight[10];
for(i=0;i<10;i++){
dight[i]=s%3;
s/=3;
}
for(i=0;i<10;i++){
if(dight[i]){
if((i&1)&&dight[i]==1)return false;
if(!(i&1)&&dight[i]==2)return false;
}
}
return true;
}
int get_news(int s,int x){
int i;int dight[10];
for(i=0;i<10;i++){
dight[i]=s%3;
s/=3;
}
if(dight[x]==0)//0 1 2 变换
dight[x]=1;
else if(dight[x]==1)
dight[x]=2;
else if(dight[x]==2)
dight[x]=1;
int news=0;//,tmp=1;
for(i=9;i>=0;i--){
news=news*3+dight[i];
//tmp*=3;
}
return news;
}
ll dfs(int cur,int s,int e,int z){
if(cur<0) return check(s);
if(!e&&!z&&dp[cur][s]!=-1) return dp[cur][s];
int endx=e?bit[cur]:9;
ll ans=0;
for(int i=0;i<=endx;i++){
if(z&&!i) ans+=dfs(cur-1,0,e&&i==endx,1);
else ans+=dfs(cur-1,get_news(s,i),e&&i==endx,0);
}
if(!e&&!z) dp[cur][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 i,j,k,t;
ll l,r;
memset(dp,-1,sizeof(dp));
scanf("%d",&t);
while(t--)
{
//memset(dight,0,sizeof(dight));
scanf("%I64d%I64d",&l,&r);
printf("%I64d\n",solve(r)-solve(l-1));
}
return 0;
}