文件详细信息

下载本文件

本文件的大小为 1796 字节。

/*
## 题目大意

一个数被称为是平衡的数，当且仅当对于所有出现过的数位（即 $0-9$），每个偶数出现奇数次，每个奇数出现偶数次。给定 $A,B$，请统计出 $[A,B]$ 内所有平衡数的个数。

保证 $1 \le A \le B \le 10^{19}$。
*/
#include<cstdio>
#include<cstring>
template<typename T>
void read(T&num){
	int ch=getchar();
	num=0;
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
}
template<typename T>
void write(T a){
	static int ch[20],cnt=0;
	if(a==0)putchar('0');
	while(a)ch[cnt++]=a%10|48,a/=10;
	while(cnt)putchar(ch[--cnt]);
}
typedef long long ll;
const int sz=10,pw3[sz+1]={1,3,9,27,81,243,729,2187,6561,19683,59049},maxstate=59049;
int T;
ll a,b;
int digit[20],cnt,status[20][sz];
ll f[20][maxstate];
ll dfs(int cur,int lim,int zero,int state){
	if(!lim&&!zero&&f[cur][state]!=-1)return f[cur][state];
	int tmp=state;
	for(int i=0;i<sz;i++){
		status[cur][i]=tmp%3;
		tmp/=3;
	}
	if(!cur){
		for(int i=0;i<10;i+=2)
			if(status[cur][i]==2){
				if(!lim&&!zero)f[cur][state]=0;
				return 0;
			}
		for(int i=1;i<10;i+=2)
			if(status[cur][i]==1){
				if(!lim&&!zero)f[cur][state]=0;
				return 0;
			}
		if(!lim&&!zero)f[cur][state]=1;
		return 1;
	}else{
		int d=lim?digit[cur]:9;
		ll ans=0;
		for(int i=0;i<=d;i++)
			if(zero&&i==0)ans+=dfs(cur-1,lim&&i==d,1,state);
			else if(status[cur][i]==2)ans+=dfs(cur-1,lim&&i==d,0,state-pw3[i]);
			else ans+=dfs(cur-1,lim&&i==d,0,state+pw3[i]);
		if(!lim&&!zero)f[cur][state]=ans;
		return ans;
	}
}
ll solve(ll x){
	cnt=0;
	while(x){
		digit[++cnt]=x%10;
		x/=10;
	}
	memset(f,-1,sizeof(f));
	return dfs(cnt,1,1,0);
}
int main(){
	read(T);
	while(T--){
		read(a),read(b);
		write(solve(b)-solve(a-1)),putchar('\n');
	}
	return 0;
}