用组合数解决P8764 二进制问题

· · 题解

其它题解都是数位 dp，我来发一篇用组合数的求解。

题意

求 1 到 n 中有多少个数满足其二进制表示中恰好有 k 个 1。

思路

首先我们举一个简单的例子：当二进制下的 n=10000， k=2 时，怎么求解答案？

可以发现， n=10000 本身只有一个 1，不符合题意，所以现在我们就是要在其它数即 0000 到 1111 找到两个 1，答案为 C_4^2。

我们再来看一个更一般的例子：当二进制下的 n=1010100， k=3 时，怎么求解答案？

同样，我们可以先枚举低六位，在 000000 到 111111 找到三个 1；再在 1000000 到 1001111 找到三个 1，这其实就相当于枚举低四位，在 0000 到 1111 找到两个 1；然后在1010000 到 1010011 找到三个 1，这其实就相当于枚举低两位，在 00 到 11 找到一个 1，最后再看 n 本身满不满足题意，这样我们就把 1 到 n 中的所有数都枚举了一遍，最终答案为 C_6^3+C_4^2+C_2^1+1。

现在我们应该就能发现解决这个问题的一般方法了：从左往右扫 n 的每一位，如果发现该位为 1，右边还有 a 位，那么答案贡献为 C_a^{k-cnt+1}， cnt 为当前发现为 1 的位数，当然需要满足 0 \leq k-cnt+1 \leq a。

代码

#include <iostream>
#define int long long
using namespace std;
long long C(long long b, long long a) // 计算组合（b在下面，a在上面）
{
    long long sum = 1;
    for (long long i = b, j = 1; j <= a; i--, j++)
        sum = sum * i / j;
    return sum;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    int cnt = 0, ans = 0;
    if (n == k && k == 1)
    {
        ans = 1;
        cout << ans;
        return 0;
    }
    for (int i = 62; i >= 1; --i)
    {
        if (k - cnt + 1 == 0)
            break;
        if ((1ll << i) & n)
        {
            cnt++;
            if (i >= k - cnt + 1)
                ans += C(i, k - cnt + 1);
        }
    }
    if (cnt == k)
        ans++;
    cout << ans;
    return 0;
}