SP10606 BALNUM - Balanced Numbers 题解

题目链接：SP10606 BALNUM - Balanced Numbers

题意：

一个数被称为是平衡的数

当且仅当对于所有出现过的数位（即 \(0\) 到 \(9\) ）

每个偶数出现奇数次，每个奇数出现偶数次。

给定 \(A,B\)，请统计出 \([A,B]\) 内所有平衡数的个数。

\(1\leq A\leq B\leq 10^{19}\)

数位dp就是套板子，然后我现在还没记住板子（

考虑记录每个数的奇偶性，用状态 st 表示

第 \(i(1\le i \le 9)\) 位为 \(0\) 表示出现次数为偶，否则为 \(1\)

再记录一个 vis ，表示这个数是否出现了

这两个东西可以压到一个 pair 里，这样方便开数组（和其他题解学的

因为这道题是统计出现次数的，所以前导零会影响计数

所以还要记录一下有没有前导零，代码里用 qd0 表示了（

最后 check 一下状态啥的，就好了（

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
#include <map>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> P;
#define F first
#define S second
#define N (int)(1.5e6+15)

int tot,num[33],f[33][N];
map<P,int> mp;
bool check(int st,int vis)
{
    for(int i=0; i<=9; i++)
    {
        if((vis>>i)&1)
        {
            if((i&1) && ((st>>i)&1)) return 0; // odd but odd
            if((!(i&1)) && (!((st>>i)&1))) return 0; // even but even
        }
    }
    return 1;
}
int dfs(int u,int st,int vis,bool limit,bool qd0)
{
    if(!u) return check(st,vis);
    if((!limit) && (!qd0) && f[u][mp[{st,vis}]]!=-1)
        return f[u][mp[{st,vis}]];
    int res=0,up=limit?num[u]:9;
    for(int i=0; i<=up; i++)
    {
        if(qd0&&(!i))res+=dfs(u-1,st,vis,limit&&i==num[u],1);
        else res+=dfs(u-1,st^(1<<i),vis|(1<<i),limit&&i==num[u],0);
    }
    if((!limit)&&(!qd0)) mp[{st,vis}]=++tot,f[u][tot]=res;
    return res;
}
int solve(int x)
{
    int cnt=0;
    while(x) num[++cnt]=x%10,x/=10;
    return dfs(cnt,0,0,1,1);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    memset(f,-1,sizeof(f));
    int Q,l,r; cin >> Q;
    while(Q--)
    {
        cin >> l >> r;
        cout << solve(r)-solve(l-1) << '\n';
    }
    return 0;
}