Description:

$[L,R]$ 内二进制表示 $0$ 的个数大于 $1$ 的个数的数的个数。

$1\le L \le R \le 2\times 10 ^{9}$

Solution:

数位 $DP$ ，状态里记一个 $sum_0$ 一个 $sum_1$ ，注意对于前导零不计算在内，开一个 $bool$ $reach$ 表示是否到了数字部分， $reach$ 初值为 $false$ ，遇到第一个 $1$ 设成 $true$ 。

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

typedef long long ll;

ll l,r;

#define MAXL 33

int len,bit[MAXL];

ll f[MAXL][MAXL][MAXL];

ll dfs(int pos,int sum0,int sum1,bool reach,bool bord)

{

	if(pos == 0)

	{

		if(sum0 >= sum1)return 1;

		else return 0;

	}

	if(!bord && f[pos][sum0][sum1] != -1)return f[pos][sum0][sum1];

	ll res = 0;

	int limit = (bord ? bit[pos] : 1);

	for(int i = 0;i <= limit;++i)

	{

		res += dfs(pos - 1,sum0 + (i == 0 && reach),sum1 + (i == 1),(reach || i),(bord && (i == limit)));

	}

	if(!bord)f[pos][sum0][sum1] = res;

	return res;

}

ll calc(ll t)

{

	len = 0;

	memset(bit,0,sizeof(bit));

	while(t > 0)

	{

		bit[++len] = (t & 1);

		t = t >> 1;

	}

	memset(f,-1,sizeof(f));

	ll res = dfs(len,0,0,false,true);

	return res;

}

int main()

{

	cin >> l >> r;

	cout << calc(r) - calc(l - 1) << endl;

	return 0;

}