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;
}