自动搬运

查看原文

来自洛谷，原作者为

	安安安年 **

搬运于2025-08-24 22:42:14，当前版本为作者最后更新于2023-05-06 17:18:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

其它题解都是数位 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;
}