题目大意：前一个区间里二进制表示状态下0的个数不小于1的个数的数的个数；
题目解析：定义dp[i][j]表示在i位上0个个数和1的个数的差值的个数，因为会产生负值所以临界值可以设置为32，这道题前导0会有影响，所以需要特别考虑；
AC代码：
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> using namespace std; int dp[40][65],n,m,num[40]; int dfs(int pos,int sum,bool lead,bool limit) { if(pos==-1) return sum>=32; if(!limit&&!lead&&dp[pos][sum]!=-1) return dp[pos][sum]; int u=limit?num[pos]:1; int ans=0; for(int i=0;i<=u;i++) { if(lead&&i==0) ans+=dfs(pos-1,sum,lead,limit&&i==num[pos]); else ans+=dfs(pos-1,sum+(i==0?1:-1),lead&&i==0,limit&&i==num[pos]); } if(!limit&&!lead) return dp[pos][sum]=ans; return ans; } int cal(int x) { int pos=0; while(x) { num[pos++]=x&1; x>>=1; } return dfs(pos-1,32,true,true); } int main() { memset(dp,-1,sizeof(dp)); while(scanf("%d%d",&n,&m)!=EOF) { printf("%d\n",cal(m)-cal(n-1)); } }