https://www.acwing.com/problem/content/341/
求ab之间的二进制表示0的数量大于等于1的数量的数的个数，注意特判0也是合法。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int a[40];
ll dp[40][40][40];
ll dfs(int pos, int s1, int s2, bool lead, bool limit) {
if(pos
== -1) {
if(s1 >= s2)
return 1;
else
return 0;
}
if(!limit && !lead && dp[pos][s1][s2] !=
-1)
return dp[pos][s1][s2];
int up = limit ? a[pos] : 1;
ll ans = 0;
for(int i = 0; i <= up; i++) {
int ns1 = s1 + ((!lead) && i == 0);
int ns2 = s2 + (i == 1);
ans += dfs(pos - 1, ns1, ns2, lead && i == 0, limit && i == a[pos]);
}
if(!limit && !lead)
dp[pos][s1][s2] = ans;
return ans;
}
ll solve(ll x) {
if(x < 0)
return 0;
int pos = 0;
while(x) {
a[pos++] = x % 2;
x /= 2;
}
return dfs(pos - 1, 0, 0, true, true);
}
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
#endif
memset(dp, -1, sizeof(dp));
ll le, ri;
while(~scanf("%lld%lld", &le, &ri)) {
printf("%lld\n", solve(ri) - solve(le - 1));
}
}
