给出区间$[A, B]$,求出区间内的数转成二进制后$0$比$1$多的数的个数
$1 \leqslant A, B \leqslant 2,000,000,000$
比较zz的数位dp
直接在二进制下dp就好
$f[i][ze][on]$表示第$i$位,填了$ze$个$0$,$on$个1的方案数
#include<cstdio>
#include<cstring>
#include<iostream>
// #include<map>
using namespace std;
#define LL long long
const LL MAXN = 101;
LL A, B;
LL num[MAXN], tot, f[MAXN][MAXN][MAXN];
LL dfs(LL x, bool lim, LL ze, LL on) {
if(x == 0) return
(ze != -1) && (on != -1) && (ze >= on);
if(!lim && f[x][ze][on]) return f[x][ze][on];
LL ans = 0;
for(LL i = 0; i <= (lim ? num[x] : 1); i++) {
if(i == 0) ans += dfs(x - 1, lim && (i == num[x]), ze == -1 ? 1 : ze + 1, on);
else {
if(on == -1) ans += dfs(x - 1, lim && (i == num[x]), 0, 1);
else ans += dfs(x - 1, lim && (i == num[x]), ze, on + 1);
}
}
if(!lim) f[x][ze][on] = ans;
return ans;
}
LL solve(LL x) {
tot = 0;
while(x) num[++tot] = x % 2, x >>= 1;
return dfs(tot, 1, -1, -1);
}
int main() {
cin >> A >> B;
cout << solve(B) - solve(A - 1);
return 0;
}
/*
1234 4444
2
*/