2021第十二届蓝桥杯国赛-H二进制问题

题面

【问题描述】

小蓝最近在学习二进制。他想知道 1 到 N 中有多少个数满足其二进制表示中恰好有 K 个 1。你能帮助他吗？

【输入格式】

输入一行包含两个整数 N 和 K。

【输出格式】

输出一个整数表示答案。

【样例输入】

7 2

【样例输出】

3

【评测用例规模与约定】

对于 30% 的评测用例，1 ≤ N ≤ 10⁶ , 1 ≤ K ≤ 10。

对于 60% 的评测用例，1 ≤ N ≤ 2 × 10⁹ , 1 ≤ K ≤ 30。

对于所有评测用例，1 ≤ N ≤ 10¹⁸ , 1 ≤ K ≤ 50。

思路

1. 暴力骗分（30%样例）

暴力枚举每一位二进制位选为 1 还是 0，每个分支组合出的数字满足条件则答案累加。

2. 数学方法（100%样例）。分析见下

记 $N$ 为如下形式，$a_i$ 表示 $N$ 的二进制表示下 第 $i$ 位 为的值（0或1），可以看出当 $N>0$ 时， $a_{n-1}=1$。

$N = a_{n-1}a_{n-2}\cdots a_1a_0$

则我们要求的结果为：

$calc(a_{n-1}a_{n-2}\cdots a_1a_0, k) = \begin{cases} solve(a_{n-1}00\cdots 00, k) &(1)\\ calc(a_{n-2}\cdots a_1a_0, k-1) &(2) \end{cases}$

上述式子中，结果由两部分的和组成，$calc(a_{n-1}a_{n-2}\cdots a_1a_0, k)$ 表示在 $[0, a_{n-1}a_{n-2}\cdots a_1a_0]$ 所表示的二进制区间内的数中，恰好有 $k$ 个二进制位为 1 的数的个数。

$(1)$ 式子表示，在 小于二进制数$a_{n-1}00\cdots 00$的数 中，有多少个恰好为 $k$ 个 1 的二进制数。可以看出，该范围内的数在区间 $[0, 11\cdots 11]$（右区间为 $n - 1$ 个1）内，要找到其恰好 $k$ 个 1 的数，及在 $n-1$ 个二进制位上找到恰好有 $k$ 个位置为 1 的个数，显然，由组合的定义，其结果即为 $C_{n-1}^{k}$。

$(2)$ 式子表示，在以最高位 $a_{n-1}$ 占据了 1 个 1 的二进制位后，剩余的二进制位所表示的数中恰好能有 $k-1$ 个（因为最高位占了一个1，所以剩余要求的为 $k-1$ 个） 1 的数的个数，即求二进制区间 $[a_{n-1}0\cdots00, a_{n-1}a_{n-2}\cdots a_1a_0]$ 表示的数中 恰好 $k$ 个 二进制位为 1 的数的个数。我们去掉最高位占据 1 的二进制位，进一步得到要求的为二进制区间 $[0,a_{n-2}\cdots a_1a_0]$ 表示的数中 恰好占据 ${k-1}$ 个 而二进制位的数的个数，则可以递归地又将其表示为$(1)$ 和 $(2)$ 两部分组成的和。

具体细节参考代码。

代码

1. 暴力骗分

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
LL n, ans;
int k, dep;

void dfs(int u, int c, LL s) {
    if (u == dep) {
        if (c == k) ans++;
        return;
    }

    LL t = s + (1ll << u);
    if (c < k && t <= n) dfs(u + 1, c + 1, t);
    dfs(u + 1, c, s);
}

int main() {
    cin >> n >> k;
    dep = log(n + 1) / log(2) + 1;
//    cout << dep << endl;
    dfs(0, 0, 0);
    cout << ans << endl;

    return 0;
}

2. 数学方法

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
int a[70];
LL n;
int k;

//快速幂
LL qpow(LL a, int n) {
    LL s = 1;
    while (n) {
        if (n & 1) s *= a;
        a *= a;
        n >>= 1;
    }
    return s;
}

//获取 x 二进制中的第一个 1 的位置
int getOne(LL x) {
    for (int i = 63; i >= 0; i--) {
        if (x >> i & 1) return i;
    }
    return -1;
}

//分解质因数
void divd(int x, int v) {
    for (int i = 2; i <= x; i++) {
        if (x % i == 0) {
            while (x % i == 0) {
                a[i] += v;
                x /= i;
            }
        }
    }
    if (x > 1) a[x] += v;
}

//求组合数 C(n,m)
LL C(int n, int m) {
    if (n < m) return 0;
    if (m == 1) return n;
    if (m == n) return 1;
    memset(a, 0, sizeof a);
    LL ans = 1;
    for (int i = n - m + 1; i <= n; i++) divd(i, 1);
    for (int i = 2; i <= m; i++) divd(i, -1);
    for (int i = 2; i <= 65; i++) {
        if (a[i]) ans *= qpow(i, a[i]);
    }
    return ans;
}

LL calc(LL n, int k) {
    if (k == 0) return 1;
    if (n == 0) return 0;
    int t = getOne(n);
    LL x = C(t, k);
    LL y = calc(n ^ (1ll << t), k - 1);
    return x + y;
}

int main() {
    cin >> n >> k;
    cout << calc(n, k) << endl;
    return 0;
}