题意：在区间中，他们化成2进制的数的0的个数大于等于1的数有多少个。
思路：我们需要记录上一次0和1的个数，此外我们还要特别注意一下前导0。
如果前面全是0的时候我们就要注意下一位是不是还是0，如果一直都是0那么这个数也满足条件。
/* gyt Live up to every day */ #include<cstdio> #include<cmath> #include<iostream> #include<algorithm> #include<vector> #include<stack> #include<cstring>3 #include<queue> #include<set> #include<string> #include<map> #include <time.h> #define PI acos(-1) using namespace std; typedef long long ll; typedef double db; const int maxn = 100+10; const ll maxm = 1e7; const int mod = 1000000007; const int INF = 1<<30; const db eps = 1e-9; const ll Max=1e19; int a[maxn]; ll dp[maxn][maxn][maxn]; ll dfs(int pos, int num0, int num1, int limit, int ncan) { if (pos==-1) { if (ncan) return 1; if (num0>=num1) return 1; return 0; } if (!limit && !ncan && dp[pos][num0][num1]!=-1) return dp[pos][num0][num1]; int up=limit?a[pos]:1; ll tmp=0; for (int i=0; i<=up; i++) { if (ncan) { if (i==0) tmp+=dfs(pos-1, 0, 0, limit&&i==a[pos], 1); else tmp+=dfs(pos-1, 0, 1, limit&&i==a[pos], 0); } else { if (i==0) tmp+=dfs(pos-1, num0+1, num1, limit&&i==a[pos], 0); else tmp+=dfs(pos-1, num0, num1+1, limit&&i==a[pos], 0); } } if (!limit) dp[pos][num0][num1]=tmp; return tmp; } ll deal(ll x) { int pos=0; while(x) { a[pos++]=x%2; x/=2; } dfs(pos-1, 0, 0, 1, 1); } void solve() { ll n, m; scanf("%lld%lld", &n, &m); memset(dp, -1, sizeof(dp)); ll a=deal(m), b=deal(n-1); //cout<<a<<" "<<b<<endl; printf("%lld ", a-b); } int main() { int t=1; //freopen("in.txt", "r", stdin); //scanf("%d", &t); for (int T=1; T<=t; T++) { solve(); } }