Round Numbers（poj 3252）

题意：算出区间内二进制中0的个数大于等于1的个数的数字有多少个

/*
  本来以为用数位DP搞，但是组合数更简单。
  我们设n的二进制长度为len。 
  ①：先考虑长度小于len的数字。
      这里以数字22为例，二进制拆成10110，len=5。
      len=1时，只能是1（题目要求是正数）；
      len=2时，第一位是1，剩下的1位，至少有1个0，ans+=C(1,1);
      …… 
        len=k时，第一位是1，剩下的len-k位，如果至少要有p个0，那么ans+=C(len-k,p)+...+C(len-k,len-k)。
  ②：再考虑长度等于len的数字。
      第一位是1。  
      第二位是0，所以第二位不能为1，必须是0。 
      第三位为0的话，后面两位可以有1个0，2个0，ans+=C(2，1)+C(2，2)。 
      接下来把第三位恢复为1，看第四位。假如第四位是0，后面一位必须是0，ans+=C(1，1)。  
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
#define N 51
#define lon long long
using namespace std;
int c[N][N];
void getc(){
    for(int i=1;i<N;i++)
        for(int j=0;j<=i;j++){
            if(j==0||i==j) c[i][j]=1;
            else c[i][j]=c[i-1][j]+c[i-1][j-1];
        }        
}
lon solve(lon n){
    if(n==1) return 0;
    lon ans=0;
    int a[N]={0},len=0;
    while(n){
        a[++len]=n%2;
        n>>=1;
    }
    reverse(a+1,a+len+1);
    for(int i=1;i<len;i++)
        for(int j=(i-1)/2+1;j<i;j++)
            ans+=(lon)c[i-1][j];
    int p0=0,p1=1;
    for(int i=2;i<len;i++){
        if(!a[i]) {p0++;continue;}
        for(int j=len-i;2*j+p0+1>=p1+len-i;j--)
            ans+=(lon)c[len-i][j];
        p1++;
    }
    if(a[len]&&p0+1>=p1) ans++;
    return ans;
}
int main(){
    getc();
    lon a,b;
    cin>>a>>b;
    cout<<solve(b+1)-solve(a);
    return 0;
}