本文同步更新于洛谷博客

题目描述

求 \(l\le x\le r\) 中所有满足 \(x_{(b)}\) 中各个数码均出现偶数次的 \(x\) 的个数。

题解

由于最多只有 \(10\) 个不同的数字，因此我们可以对每个数字出现的个数进行二进制状态压缩，\(0\) 表示出现偶数次，\(1\) 表示出现奇数次。下面说一下状态如何转移，因为我们每次要将某一位上的 \(0\) 变为 \(1\)，\(1\) 变为 \(0\)，因此我们将 \(sta\) 与 \(2^i\) 按位异或即可（\(i\) 表示填入的数）。
接下来就是的数位 dp 了，我们传四个参数 \(k,sta,p,q\) 进入 dfs，分别表示枚举到第 \(k\) 位，当前每个数字出现次数的状态，是否为前导 \(0\)，以及这一位填的数有没有限制，用 \(f\) 数组记忆化即可。

注意

• 我们不用计算 \(sta\) 中 \(1\) 的个数，因为当且仅当 \(sta=0\) 时所有数码出现的次数均为偶数
• 只有将 \(f\) 数组添加一维表示当前的数是 \(b\) 进制才能只初始化一遍，我第一次就是因为这个 WA 了。

Code

#include
using namespace std;
#define ll long long
int q,b,len,a[65];
ll l,r,f[11][65][1024];
ll dfs(int k,int sta,int p,int q)
{
    if(!k)
	return !sta;
    if(!p&&!q&&f[b][k][sta]!=-1)
	return f[b][k][sta];
    int y=q?a[k]:(b-1);
    ll res=0;
    for(int i=0;i<=y;i++)
	res+=dfs(k-1,(p&&!i)?0:(sta^(1<