SPOJ 上 AC：https://www.luogu.com.cn/record/165748445

洛谷 IDE 测样例显示 MLE。

代码：

#include<bits/stdc++.h>
using namespace std;
/*
当前位数，奇偶性，是否出现，末尾，前导零
利用 map 对二进制数编号
*/
const int N=1.5e6+7;
int tot,a[60],cnt;
long long f[30][N];
unordered_map<int,int> m[2000];
bool check(int n,int m){
	for(int i=0;i<=9;i++){
		if(m&(1<<i)){
			if(!(i&1)&&!(n&(1<<i))) return 0;//偶数出现偶数次
			if((i&1)&&(n&(1<<i))) return 0;//反之
		}
	}
	return 1;
}
long long dfs(int u,int oj,int ap,bool lim,bool zero){
	if(u==0) return check(oj,ap);
	if(!zero&&!lim&&f[u][m[oj][ap]]!=-1) return f[u][m[oj][ap]];
	long long ans=0;
	int ed=lim?a[u]:9;
	for(int i=0;i<=ed;i++){
		bool fl=zero&&(!i);//前导零
		ans+=dfs(u-1,fl?oj:oj^(1<<i),fl?ap:ap|(1<<i),lim&&i==a[u],fl);
	}
	if(!lim&&!zero) m[oj][ap]=++cnt,f[u][cnt]=ans;
	return ans;
}
long long calc(long long k){
	tot=0;
	while(k) a[++tot]=k%10,k/=10;
	return dfs(tot,0,0,1,1);
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	memset(f,-1,sizeof f);
	int T;
	cin>>T;
	long long l,r;
	while(T--){
		cin>>l>>r;
		cout<<calc(r)-calc(l-1)<<'\n';
	}
	return 0;
}