Balanced Numbers

思路：

没特殊声明，在本题0算偶数，不要把前导零算进来了

数位入门题，我又写了一堆，开始不知道算不算，就瞎写了一个，结果答案大了，如何算上又把前导零算上了，特判前导零但为了少写一个参数直接硬写，然后写错了。时因为是两遍，以为是一遍，然后出现了不能解释的结果。

把每个数位是否出现状压到的二进制位里，一个整数的二进制位通过异或来表示某个数位出现的次数是奇数次还是偶数次。

，表示当前为第len位，出现的数位的集合cnt，每个数位出现次数奇偶的集合pos，表示len个数位使得cnt里的数位合法或者使新添的数位合法的方案数，这是唯一的。

Code：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include <vector>
#include<map>
#include<set>
#include<utility>
using namespace std;
typedef long long ll;
inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
ll dp[21][1<<10][1<<10];
int digit[21];
ll dfs(int len,int pos,int cnt,bool limit,bool zero) {
    if(!len) {
        if(cnt==1) return 1;
        for(int i=0,x;i<=9;++i) {
            x=1<<i;
            if(cnt&x) {
                if(i&1 && pos&x) return 0;
                else if(!(i&1) && !(pos&x)) return 0;
            }
        }
        return 1;
    }
    if(!limit&&dp[len][pos][cnt]!=-1) return dp[len][pos][cnt];
    int endi=(limit?digit[len]:9);
    ll ans=0;
    for(int i=0;i<=endi;++i) {
        bool op=(zero&&i==0);
        ans+=dfs(len-1,op?0:(pos^(1<<i)),op?0:cnt|(1<<i),limit&&i==endi,op);
    }
    if(!limit) dp[len][pos][cnt]=ans;
    return ans;
}
ll solve(ll x) {
    int len=0;
    while(x) {
        digit[++len]=x%10;
        x/=10;
    }
    return dfs(len,0,0,true,true);
}
int main() {
    int t=read();
    ll l,r;
    memset(dp,-1,sizeof dp);
    while(t--) {
        l=read(),r=read();
        printf("%lld\n",solve(r)-solve(l-1));
    }
    return 0;
}