[SP10606] BALNUM - Balanced Numbers 解题记录

[SP10606] BALNUM - Balanced Numbers 解题记录

题意简述

求出 $[l,r]$ 中，数位中的奇数出现过偶数次并且偶数出现过奇数次的数的个数。

题目分析

数位 DP。
考虑记录 $0\sim 9$ 中每个数出现的奇偶次，记录下来，但是这样就需要开很多维数组，代码复杂度很高，所以考虑状压。
用两个二进制数 $s,cnt$ 记录每个数字的出现情况和出现次数情况。其中 $s$ 的第 $i$ 位表示数字 $i$ 是否出现过，$cnt$ 的第 $i$ 位表示数字 $i$ 出现过奇数次还是偶数次。
返回的时候检查当前状态 $(s,cnt)$ 是否合法，如果发现一个奇数出现过奇数次或者一个偶数出现过偶数次，那么直接返回 $0$ 即可。
设 $d{p}_{pos,s,cnt}$ 表示填到第 $pos$ 位，出现状态为 $s$，且出现次数状态为 $cnt$ 的“平衡数”的个数。
注意：当有前导 $0$ 时不应更新 $0$ 的状态。

AC Code

#include<bits/stdc++.h>
#define arrout(a,n) rep(i,1,n)std::cout<<a[i]<<" "
#define arrin(a,n) rep(i,1,n)a[i]=read()
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define dep(i,x,n) for(int i=x;i>=n;i--)
#define erg(i,x) for(int i=head[x];i;i=e[i].nex)
#define dbg(x) std::cout<<#x<<":"<<x<<" "
#define mem(a,x) memset(a,x,sizeof a)
#define all(x) x.begin(),x.end()
#define arrall(a,n) a+1,a+1+n
#define PII std::pair<int,int>
#define m_p std::make_pair
#define u_b upper_bound
#define l_b lower_bound
#define p_b push_back
#define CD const double
#define CI const int
#define int long long
#define il inline
#define ss second
#define ff first
#define itn int
int read() {
    char ch=getchar();
    int r=0,w=1;
    while(ch<'0'||ch>'9') w=ch=='-'?-1:w,ch=getchar();
    while(ch>='0'&&ch<='9') r=r*10+ch-'0',ch=getchar();
    return r*w;
}
CI N=1050;
int T,l,r,a[N],num[N],dp[20][N][N];
bool check(int s,int cnt) {
    rep(i,0,9) {
        if((s>>i)&1) {//如果i出现过
            if((i&1)/*i是奇数*/&&((cnt>>i)&1)/*i出现过奇数次*/) {
                return 0;
            }
            if(!(i&1)/*i是偶数*/&&!((cnt>>i)&1)/*i出现过偶数次*/) {
                return 0;
            }
        }
    }
    return 1;
}
int dfs(int pos,int s,int cnt,bool st,bool limit) {
    if(pos>a[0]) {
        return check(s,cnt);
    }
    if(~dp[pos][s][cnt]&&!st&&!limit) {
        return dp[pos][s][cnt];
    }
    int up=limit?a[a[0]-pos+1]:9,ans=0;
    rep(i,0,up) {
        if(st&&!i) {/*有前导0且当前填0*/
            ans+=dfs(pos+1,s,cnt,1,limit&&(i==up));//不做更改
        } else {
            ans+=dfs(pos+1,s|(1<<i)/*更新第i位*/,cnt^(1<<i)/*奇变偶，偶变奇*/,st&&!i,limit&&(i==up));
        }
    }
    if(!st&&!limit) {
        dp[pos][s][cnt]=ans;
    }
    return ans;
}
int solve(int x) {
    a[0]=0;
    while(x) {
        a[++a[0]]=x%10;
        x/=10;
    }
    mem(dp,-1);
    return dfs(1,0,0,1,1);
}
signed main() {
    T=read();
    while(T--) {
        l=read(),r=read();
        std::cout<<solve(r)-solve(l-1)<<"\n";
    }
    return 0;
}