题目链接：POJ3252


题意很简单：【L，R】区间中，各个数的二进制表示形式中0的个数不小于1的个数的数目


本来是可以1A的简单题，超时了无数发，来解释解释细节

看到题目中L，R的大小是2*10^9，在int范围内，超时跟long long可能也有关系


然后就是状态的分析

dp【pos】【x】【y】：当前枚举到了第pos位，0的个数有x个，1的个数有y个，符合题目意义的值有多少个

由于前导0对于题目影响，所以需要一个bool型变量zero来标记当前情况下是不是前面全都是全导0，然后呢，dfs记忆化的模板也出来了


int dfs（int pos，int x，int y，bool zero，bool flag）

zero==0前面全是前导0
zero==1前面有某个1

当pos==0的时候，就需要判断这个数是不是符合条件了

第一种情况呢，就是没有前导0了，并且0的个数不少于1的个数

第二种情况呢，就是全是前导0，也就是zero=0


超时主要是在记忆化这块的：

判断能否记忆化，只与当前的flag标记有关，意思是高低位的值影响，当前有没有前导0是不影响的

if (flag&&dp[pos][x][y]!=-1) return dp[pos][x][y];

如果在这加了zero的判断的话，会浪费很多时间在不需要的计算上，当然超时


但是在记录的时候，是需要判断zero标记位的

这道题有没有zero判断不会错，但是：HDOJ3967

这个题必须判断zero，我也不明白为什么


还有1点就是转移的时候，要根据是不是前导0和当前填写的也是0来判断要不要把这次枚举的0或者1的数位值统计到x和y上


#include<map>
#include<set>
#include<math.h>
#include<time.h>
#include<iostream>
#include<cstdio>
#include<queue>
#include<stack>
#include<stdio.h>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<cstdlib>
using namespace std;

#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define ll rt<<1
#define rr rt<<1|1
#define LL long long
#define ULL unsigned long long
#define maxn 1050
#define maxnum 1000050
#define eps 1e-6
#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)

int dp[50][80][80];
int digit[50];

int dfs(int pos,int x,int y,bool zero,bool flag){
	//zero==0前面全是前导0
	//zero==1前面有某个1 
	if (pos==0) return (zero&&x>=y)||(zero==0);
	if (flag&&dp[pos][x][y]!=-1) return dp[pos][x][y];
	int maxnumber=flag?1:digit[pos];
	int ans=0;
	for(int i=0;i<=maxnumber;i++)
		if (zero==0&&i==0)
			ans+=dfs(pos-1,x,y,0,flag||i<maxnumber);
		else
			ans+=dfs(pos-1,x+1-i,y+i,zero||i,flag||i<maxnumber);
	if (flag&&zero) dp[pos][x][y]=ans;
	return ans;
}

int calc(int n){
	if (n<0) return 0;
	int len=0;
	while(n){
		digit[++len]=n%2;
		n/=2;
	}
	return dfs(len,0,0,0,0);
}

int A,B;

int main(){
	//input;
	memset(dp,-1,sizeof(dp));
	while(scanf("%d%d",&A,&B)!=EOF)
		printf("%d\n",calc(B)-calc(A-1));
	//printf("%I64d\n",calc(A-1));
	//printf("%I64d\n",calc(B));
	return 0;
}