Balanced Numbers (数位DP)

Balanced Numbers

https://vjudge.net/contest/287810#problem/K

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 <= 10 ¹⁹

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

用三进制来计算数位出现的奇偶

 #include<bits/stdc++.h>
 using namespace std;
 #define lson l,mid,rt<<1
 #define rson mid+1,r,rt<<1|1
 #define sqr(x) ((x)*(x))
 #define pb push_back
 #define eb emplace_back
 #define maxn 13000005
 #define eps 1e-8
 #define pi acos(-1.0)
 #define rep(k,i,j) for(int k=i;k<j;k++)
 typedef long long ll;
 typedef pair<int,int> pii;
 typedef pair<long long,int>pli;
 typedef pair<int,char> pic;
 typedef pair<pair<int,string>,pii> ppp;
 typedef unsigned long long ull;
 const long long MOD=1e9+;
 /*#ifndef ONLINE_JUDGE
         freopen("1.txt","r",stdin);
 #endif */

 ll dp[][];
 int a[];
 int k;

 bool Check(int x){
     int num[];
     for(int i=;i<;i++){
         num[i]=x%;
         x/=;
     }
     for(int i=;i<;i++){
         if(num[i]==&&(i%)){
             return false;
         }
         if(num[i]==&&(i%==)){
             return false;
         }
     }
     return true;
 }

 int Change(int x,int v){
     int num[];
     for(int i=;i<;i++){
         num[i]=x%;
         x/=;
     }
     if(num[v]==) num[v]=;
     else if(num[v]==||num[v]==) num[v]=;
     x=;
     for(int i=;i>=;i--){
         x=x*+num[i];
     }
     return x;
 }

 ll dfs(int pos,int st,int lead,int limit){///要去掉前导0
     if(pos==-) return Check(st);
     if(!limit&&dp[pos][st]!=-) return dp[pos][st];
     ll ans=;
     int up=limit?a[pos]:;
     for(int i=;i<=up;i++){
         ans+=dfs(pos-,(lead==&&i==)?:Change(st,i),lead&&i==,limit&&i==a[pos]);
     }
     if(!limit) dp[pos][st]=ans;
     return ans;
 }

 ll solve(ll x){
     int pos=;
     while(x){
         a[pos++]=x%;
         x/=;
     }
     ll ans=dfs(pos-,,,);
     return ans;
 }

 int main(){
     #ifndef ONLINE_JUDGE
      //   freopen("1.txt","r",stdin);
     #endif
     std::ios::sync_with_stdio(false);
     int t;
     ll n,m;
     memset(dp,-,sizeof(dp));
     cin>>t;
     for(int _=;_<=t;_++){
         cin>>n>>m;
         ll ans=solve(m)-solve(n-);
         cout<<ans<<endl;
     }

 }