Balanced Numbers （数位dp+三进制）

SPOJ – BALNUM

题意：

Balanced Numbers：数位上的偶数出现奇数次，数位上的奇数出现偶数次（比如2334, 2出现1次，4出现1次，3出现两次，所以2334是 Balanced Numbers） ，求一个区间内有多少Balanced Numbers。

解题思路：看题很容易想到数位dp，但是怎么记录某数字出现的次数呢？由于某数字出现的次数只与奇偶有关，与大小没有关系，所以我们可以分别用0,1,2来表示某数字没有出现，出现奇数次，出现偶数次，然后就可以用三进制来记录所有数字出现的情况了。（比如10的三进制是101，即表示0，2出现奇数次，1没有出现）

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<stack>
#include<cstdio>
#include<map>
#include<set>
#include<string>
#include<queue>
using namespace std;
#define inf 0x3f3f3f3f
typedef unsigned long long ll;
inline ll gcd(ll i,ll j){
return j==0?i:gcd(j,i%j);
}
inline ll lcm(ll i,ll j){
return i/gcd(i,j)*j;
}
ll dp[20][60000];
int dis[20],di[15];
int d[15],work;
int jug(int num){
int len=0;
memset(d,0,sizeof(d));
while(num){
d[len++]=num%3;
num/=3;
}
for(int i=0;i<10;i++){
if(d[i]==0)
continue;
if(i%2==0&&d[i]%2==0){
return 0;
}
else if(i%2==1&&d[i]%2==1){
return 0;
}
}
return 1;
}
int change(int num,int n){
int len=0;
memset(d,0,sizeof(d));
while(num){
d[len++]=num%3;
num/=3;
}
if(d[n]==1)
d[n]=2;
else
d[n]=1;
int ans=0;
for(int i=0;i<10;i++){
ans+=di[i]*d[i];
}
return ans;
}
ll dfs(int pos,int num,bool limit){
if(pos==-1){
work=1;
return jug(num);
}
if(!limit&&dp[pos][num]!=-1&&work)
return dp[pos][num];
int up=limit?dis[pos]:9;
ll ans=0;
for(int i=0;i<=up;i++){
if(work==1)
ans+=dfs(pos-1,change(num,i),limit&&i==up);
else
ans+=dfs(pos-1,0,limit&&i==up);
}
if(!limit)
dp[pos][num]=ans;
return ans;
}
ll solve(ll a){
int len=0;
ll ans=0;
work=0;
while(a!=0){
dis[len++]=a%10;
a/=10;
}
return dfs(len-1,0,true);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
scanf("%d",&t);
memset(dp,-1,sizeof(dp));
di[0]=1;
for(int i=1;i<=10;i++){
di[i]=di[i-1]*3;
}
while(t--){
ll l,r;
scanf("%llu%llu",&l,&r);
printf("%llu\n",solve(r)-solve(l-1));
}
return 0;
}