题目链接：https://www.luogu.com.cn/problem/P6218
题目大意：
求 ([l,r]) 范围内有多少数满足二进制表示中的 (0) 的数量大于等于 (1) 的数量。
解题思路：
数位DP，定义状态 (f[p][z][x]) 表示：
- 当前在第 (p) 位；
- (z) 对应目前是否一直是前置零（true为一直是，false为不是）；
- (x) 表示 (0) 的数量减去 (1) 的数量（因为在实现时可能存在 (x) 是负数所以实现的时候加了一个 (33) 的偏移）。
示例程序如下：
#include <bits/stdc++.h>
using namespace std;
// f[p][z][x]表示第p为，z=0个数-1个数,x
int f[33][2][66], a[33], tmp;
bool vis[33][2][66];
int dfs(int p, bool z, int x, bool limit) {
if (p == -1) {
return x >= 0 ? 1 : 0;
}
if (!limit && vis[p][z][x+33]) return f[p][z][x+33];
int res = 0, up = limit ? a[p] : 1;
for (int i = 0; i <= up; i ++) {
tmp += (1<<p) * i;
bool zz = z && i==0 && p;
int xx = x;
if (i == 1) xx --;
else if (!zz) xx ++;
res += dfs(p-1, zz, xx, limit && i==up);
tmp -= (1<<p) * i;
}
if (!limit) {
vis[p][z][x+33] = true;
f[p][z][x+33] = res;
}
return res;
}
int handle(int num) {
int p = 0;
while (num) {
a[p++] = num % 2;
num /= 2;
}
return dfs(p-1, true, 0, true);
}
int main() {
int l, r;
cin >> l >> r;
cout << handle(r) - handle(l-1) << endl;
return 0;
}