题目问区间有多少个数字的二进制0的个数大于等于1的个数。
用数学方法求出0到n区间的合法个数，然后用类似数位DP的统计思想。
我大概是这么求的，确定前缀的0和1，然后后面就是若干个0和若干个1的不重复全排列数。。
写得挺痛苦的。。另外A[i][j]表示i个0和j个1的不重复全排列数，即A[i][j]=(i+j)!/i!/j!，这个可以从A[i-1][j]或A[i][j-1]求出来，这样就不用担心乘法溢出了。
#include<cstdio>
#include<cstring>
using namespace std;
long long d[][];
long long cnt(int zero,int one,int len){
long long res=;
for(int i=; i<=len; ++i){
int j=len-i;
if(i+zero<j+one) continue;
res+=d[i][j];
}
return res;
}
long long calu(int a){
int len=;
while(len!=- && ((a>>len)&)==) --len;
if(len==-) return ;
long long res=;
for(int i=; i<len; ++i){
res+=cnt(,,i);
}
int zero=,one=;
for(int i=len-; i>=; --i){
if((a>>i)&){
res+=cnt(zero+,one,i);
++one;
}else{
++zero;
}
}
zero=; one=;
for(int i=; i<=len; ++i){
if((a>>i)&) ++one;
else ++zero;
}
return res+(zero>=one);
}
int main(){
d[][]=;
for(int i=; i<; ++i){
for(int j=; j<; ++j){
d[i+][j]=d[i][j]*(i+j+)/(i+);
d[i][j+]=d[i][j]*(i+j+)/(j+);
}
}
int a,b;
while(~scanf("%d%d",&a,&b)){
printf("%lld\n",calu(b)-calu(a-));
}
return ;
}