Round Numbers /// 组合计数 oj21455

题目大意：

给定a，b

输出[a,b]的闭区间中round number的数量

所谓round就是一个数在二进制下0的个数大于等于1的个数

0的个数>=1的个数也就是1的个数<=0的个数

那么 l 长度中， 1的个数num = l / 2 个，如：l=4 num=2， l=5 num=2

而当二进制长度为 l 时，首位肯定为1

那么应在剩下的 l-1 位中选出 0 到 l / 2 - 1 个位置为1的情况

递推出31内的组合数就够了因为 2^31 > 2e9

找到a，b二进制的位数 L，R

直接计算 L位到 R-1位的所有数量sum

L位中比a小的应该从sum中删去

R位中比b小的应该加进sum中

如：二进制同样位数下比 1010100 小的，l=7 l/2=3

（为什么不从第一个1开始后面会说）

从第二个1开始 1010000 要比它小应该将1置为0

即100_ _ _ _ 这样就是在之后的4个位置中选出 3-(2-1) 个1

(最多3个1 已经存在2个将当前位置为0 那么-1)

再到第三个1的情况 1010100 要比它小应该将1置为0

即10100_ _ 这样就是在之后的2个位置中选出 3-(3-1)个1

从第一个1开始是不能将其置为0的所以直接从第二个开始

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int bi[35];
int getNum(int x) {
    int c=0;
    while(x) {
        bi[++c]=x&1;
        x >>= 1;
    }
    return c;
}
ll C[35][35];
void init() {
    C[0][0]=C[1][0]=C[1][1]=1LL;
    for(int i=2;i<=35;i++) {
        C[i][0]=C[i][i]=1LL;
        for(int j=1;j<i;j++)
            C[i][j]=C[i-1][j-1]+C[i-1][j];
    }
}
int main()
{
    ll a,b;
    init();
    while(~scanf("%lld%lld",&a,&b)) {
        ll ans=0;
        int L=getNum(a), c=1; // 二进制位数
        for(int i=L-1;i>=1;i--)
            if(bi[i]) { c++;
                for(int j=0;j<=L/2-(c-1);j++)
                    ans-=C[i-1][j]; /// 减去L位中比a小的
            }
        int R=getNum(b); c=1;
        for(int i=R-1;i>=1;i--)
            if(bi[i]) { c++;
                for(int j=0;j<=R/2-(c-1);j++)
                    ans+=C[i-1][j]; /// 加上R位中比b小的
            }

        for(int i=L;i<R;i++) { /// 加上L位到R-1位的个数
            for(int j=0;j<i/2;j++)
                ans+=C[i-1][j];
        }
        if(c<=R/2) ans++; // 判断b是不是not round
        // a不需要判断 因为包含在L位中

        printf("%lld
",ans);
    }

    return 0;
}

View Code