牛客假日团队赛5 F- 随机数（组合数学）

可以使用组合数学或者数位dp来写
组合数的写法， 就是通过枚举1 和 0的个数来计算总的方案数

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll pre[110];
ll C(ll n, ll m) // 算组合数
{
    ll res1 = 1, j = 1;
    if (n / 2 < m)
        m = n - m;
    for (ll i = n - m + 1; i <= n; i++)
    {
        res1 *= i;
        while (res1 % j == 0 && j <= m)
        {
            res1 /= j;
            j++;
        }
    }
    return res1;
}
ll fun(ll a)
{
    ll u = 0, v = 0;
    ll ans = 0;
    ll x = a;
    ll tot = 0;
    while (x)
    {
        if (x & 1)
            u++;
        else
            v++;
        tot++;     // 该数字二进制位数
        x >>= 1;
    }
    if (u <= v && u) // 未排列也满足条件
        ans++;
    ll cnt1 = 1;
    ll cnt2 = 0;
    for (ll i = tot - 2; i >= 0; i--) // 枚举原数
    {
        if ((1LL << i) & a)   // 对二进制位上的1操作
        {
            cnt2++; // 把当前的1变为0
            if (i == 0)
            {
                if (cnt1 <= cnt2)
                    ans++;
                continue;
            }
            for (ll j = 0; cnt1 + j <= (i - j) + cnt2; j++) // 枚举1的个数
            {
                if (i >= j)   // 后面可以排的位置要大于枚举的1的个数
                    ans += C(i, j);
            }
            cnt2--;  // 再变回来
            cnt1++;  // 加上1的个数
        }
        else
            cnt2++;  // 0++
    }
    if (tot <= 1)
        return 1;
    for (ll i = 1; i < tot; i++)  // 加上低层的情况(因为低层小于当前位数， 任意排列均不会大于原数)
        ans += pre[i];
    return ans;
}
int main(){
    for (ll i = 1; i <= 32; i++)
    {
        for (ll j = 0; 1 + j <= i - 1 - j; j++) // j 是枚举 1的个数
        {
            pre[i] += C(i - 1, j);   // 打表，算每层的排列数目
        }
    }
    pre[1] = 1;
    ll a, b;
    while (cin >> a >> b)
        cout << fun(b) - fun(a - 1) << endl;
    return 0;
}