本文同步更新于洛谷博客

题目描述

一个数被称为是平衡的数，当且仅当对于所有出现过的数位，每个偶数出现奇数次，每个奇数出现偶数次。给定 \(A,B\) 请统计出 \([A,B]\) 内所有平衡数的个数。

题解

平衡数与数的大小无关，并且我们要统计一个区间内符合条件的数的个数，不难想到用数位 dp。又因为我们要统计数字出现的次数，所以需要状态压缩。
我们用 \(x\) 来表示数字出现的次数，\(0\) 表示出现偶数次，\(1\) 表示出现奇数次。现在问题来了，\(0\) 也可以表示该数字没出现过，因此需要再用一个变量 \(y\) 表示有没有出现过，\(0\) 表示没出现过，\(1\) 表示出现过。根据定义不难知道，转移的时候，\(x\) 用的是异或，\(y\) 用的是或。
接下来，我们传五个参数 \(k,x,y,p,q\) 进入 dfs，分别表示枚举到第 \(k\) 位，当前每个数字出现次数的状态，当前每个数字是否出现的状态，当前位是否为前导 \(0\)，以及这一位填的数有没有限制，用 \(f\) 数组记忆化即可。
注意到本题的内存限制是 \(1.46\mathrm{GB}\)，所以我们可以直接开 \(20\times1024\times1024\) 的数组，没有必要用其他题解说的 map，当然想用也行。

Code

#include
using namespace std;
#define ll long long
int t,len,a[20];
ll l,r,f[20][1024][1024];
ll check(int x,int y)
{
    for(int i=0;i<=9;i++)
    {
	if(y&(1<