大型补档计划
设 \(f[i][j]\) 表示二进制下，数字有 \(i\) 位， \(0\) 的个数 - \(1\) 的个数 \(=\) \(j\) 的方案数
\(f[0][0] = 1;\)
填一个 \(0\)
\(f[i + 1][j + 1] += f[i][j]\)
填一个 \(1\)
\(f[i + 1][j - 1] += f[i][j]\)
考虑到负下标越界，需要加偏移量
然后数位 dp 的细节蛮多的，比如第一位如果选 0 的话得特判，因为dp包括了前导0在内加入计算，所以得额外处理一个 \(g[i]\) 表示一共 $ <= i$ 位，符合条件的个数。
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 31, D = 30;
int a, b, d[N];
int f[N][N << 1], g[N];
void init() {
f[0][D] = 1;
for (int i = 0; i + 1 < N; i++) {
for (int j = 0; j <= D * 2; j++) {
if (!f[i][j]) continue;
if (j < D * 2) f[i + 1][j + 1] += f[i][j];
if (j) f[i + 1][j - 1] += f[i][j];
}
}
g[0] = g[1] = 1;
for (int i = 2; i < N; i++) {
g[i] = g[i - 1];
for (int j = D + 1; j <= D * 2; j++) g[i] += f[i - 1][j];
}
}
int solve(int x) {
if (x == 0) return 1;
int n;
for (int i = N - 1; ~i; i--)
if (x >> i & 1) { n = i; break; }
for (int i = 0; i <= n; i++) d[i] = x >> i & 1;
int p = 0, res = 0;
// p：目前 0 的个数 - 1 的个数
for (int i = n; ~i; i--) {
// 有 i + 1 位
if (d[i]) {
if (i == n) res += g[i];
else for (int j = D - (p + 1); j <= D * 2; j++) res += f[i][j];
p--;
} else p++;
if (i == 0 && p >= 0) res++;
}
return res;
}
int main() {
init();
scanf("%d%d", &a, &b);
printf("%d\n", solve(b) - solve(a - 1));
}