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;
}