T30212: 二进制问题

dfs, 数位dp, 排列组合, http://cs101.openjudge.cn/practice/30212/

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

输入

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

输出

输出一个整数表示答案。

样例输入

7 2

样例输出

提示

dfs, 数位 DP 对于 60% 的评测用例，1≤ N ≤10^6 对于 80% 的评测用例，1≤ N ≤10^7 对于所有评测用例，1 ≤ N≤ 10^9

来源

https://www.luogu.com.cn/problem/P8764（2025fall cs101, TA-hhy）

【沈俊丞25工院】

python

import math

n, k = map(int, input().split())
m = []
for i in range(32, -1, -1):
    if n & (1 << i):
        m.append(i)
ans = 1 if len(m) >= k else 0
for i in range(min(len(m), k)):
    ans += math.comb(m[i], k - i)
print(ans)

这是一段经典的数位统计（Digit DP / 组合数学）代码。

它的核心功能是：计算在 $0$ 到 $n$ （包含 $n$ ）的所有整数中，二进制表示下恰好包含 $k$ 个 $1$ 的数的个数。

下面我将分段解读代码，并在最后提供一个具体的例子演示。

代码详细解读与注释

python

import math

# 1. 输入处理
# n: 上界数值
# k: 目标二进制中 1 的个数
n, k = map(int, input().split())

# 2. 预处理：提取 n 的二进制特征
# m 列表存储了 n 的二进制表示中所有为 '1' 的位的索引（从低位到高位）。
# 例如：
#   如果 n = 13 (二进制 1101)
#   第 0 位是 1，第 1 位是 0，第 2 位是 1，第 3 位是 1
#   所以 m = [0, 2, 3]
m = [i for i in range(32) if n >> i & 1]

# a 代表 n 自身包含 1 的总个数（即 population count）
a = len(m)

# 3. 核心计算逻辑
# 我们要找 x (0 <= x <= n) 使得 x 的二进制有 k 个 1。
# 这种统计通常使用“从高位到低位”的策略。
# 我们遍历 n 的每一个为 1 的二进制位，尝试在这个位置“填 0”，
# 从而让生成的数 x 严格小于 n，这样剩下的低位就可以利用组合数随意填充了。

# (a >= k) 的含义：
# 这是一个布尔值（True为1，False为0）。
# 它考虑的是一种特殊情况：取 n 的最高 k 个 1 组成的数。
# 如果 n 自身的 1 的个数 a >= k，那么由 n 的前 k 个 1 组成的数肯定 <= n，且恰好有 k 个 1。
# 这相当于处理了“边界”情况。

result = (a >= k) + sum(
    # 这里的循环 i 代表：我们从高位开始，已经保留了 n 的前 i 个 1。
    # 我们现在的目标是处理 n 的第 (i+1) 个 1（从高往低数）。
    # m[a - i - 1] 就是当前处理的这个 1 所在的二进制位索引（设为 pos）。
    # 策略是：将 n 在这个位置的 1 变为 0 (使 x < n)。
    # 既然这一位变成了 0，且前面保留了 i 个 1，
    # 那么我们还需要在比 pos 更低的 (pos) 个位置中，选出 (k - i) 个位置填 1。
    
    math.comb(m[a - i - 1], k - i) 
    for i in range(min(a, k))
)

print(result)

核心算法图解

这个算法的思想是按位逼近。为了统计 $x \leq n$ ，我们从 $n$ 的最高位开始看：

假设 $n$ 的二进制是 $1101$ ( $13$ )，我们想找 $k = 3$ 个 $1$ 的数。 $m = [0, 2, 3]$ (对应位 $2^{0}, 2^{2}, 2^{3}$ )。

算法的遍历过程如下（从高位 $1$ 到低位 $1$ ）：

处理最高位的 1 (位置 3)：
- $n$ 在位置 3 是 1。如果我们把 $x$ 在这个位置设为 0，那么无论 $x$ 后面的位怎么填，都有 $x < n$ 。
- 我们在这个位置填 0。
- 我们还需要凑够 $k = 3$ 个 $1$ 。
- 剩下的低位有 $3$ 个（位置 0, 1, 2）。
- 方案数： $C (3, 3) = 1$ 。
- 对应的数是 $0111_{2} (7)$ 。
保留最高位 1，处理次高位的 1 (位置 2)：
- 现在 $x$ 的最高位确定是 1（和 $n$ 一样）。已消耗 $1$ 个 $1$ 。
- $n$ 在位置 2 是 1。我们尝试把 $x$ 在这个位置设为 0。
- 现在 $x$ 是 10...，肯定小于 $11. . .$ ( $n$ )。
- 还需要凑 $k - 1 = 2$ 个 $1$ 。
- 剩下的低位有 $2$ 个（位置 0, 1）。
- 方案数： $C (2, 2) = 1$ 。
- 对应的数是 $1011_{2} (11)$ 。
保留前两个 1，处理第三个 1 (位置 0)：
- 现在 $x$ 的前缀是 110...（位置 1 是 0，跳过）。已消耗 $2$ 个 $1$ 。
- $n$ 在位置 0 是 1。我们尝试把 $x$ 在这个位置设为 0。
- 还需要凑 $k - 2 = 1$ 个 $1$ 。
- 剩下的低位有 $0$ 个。
- 方案数： $C (0, 1) = 0$ 。没法填。
处理边界情况 (a >= k)：
- 我们前面都是在某一位把 $n$ 的 1 变成 0 来保证 $x < n$ 。
- 最后还有一种情况：如果我们完全不把 $1$ 变 $0$ ，而是尽可能匹配 $n$ 的前缀。
- $n$ 本身有 $3$ 个 $1$ ，我们的目标也是 $3$ 。
- 所以 $n$ 本身 ( $1101$ ) 也是符合条件的。
- 代码中的 (a >= k) 就是加上这 1 个计数。

最终结果： $1 + 1 + 0 + 1 = 3$ 。符合条件的数为： $7, 11, 13$ 。

总结

这段代码非常精炼地利用了组合数（math.comb）来解决数位统计问题，避免了复杂的递归或动态规划写法。

循环部分：计算所有严格小于 $n$ 的符合条件的数。
(a >= k) 部分：计算等于 $n$ 的部分（或者由 $n$ 的前 $k$ 个 1 构成的边界数）。

这个问题可以通过组合数学或数位 DP（Digit DP）的思想来解决。

解题思路

题目要求在 $1$ 到 $N$ 之间，统计二进制表示中恰好有 $K$ 个 1 的数字个数。由于 $N$ 最大可达 $10^{18}$ ，我们不能遍历每一个数，而应该利用二进制位的性质。

预处理组合数：我们需要计算从 $n$ 个位置中选出 $k$ 个位置放置 1 的方案数，即组合数 $C (n, k)$ 。可以使用帕斯卡三角形（杨辉三角）预处理出 $64 \times 64$ 以内的组合数。
数位统计（从高位向低位遍历）：将 $N$ 转化为二进制字符串。从左（最高位）向右遍历：
- 如果当前位是 1：
  - 如果我们把这一位改为 0，那么后面剩下的所有位可以任意选择。假设后面还有 rem 位，我们还需要 need 个 1，那么方案数就是 $C (r e m, n e e d)$ 。我们将这个结果累加到答案中。
  - 然后我们保持这一位为 1（即与 $N$ 的这一位相匹配），继续处理下一位，并更新已使用的 1 的个数。
- 如果当前位是 0：
  - 我们只能保持这一位为 0 才能保证结果不大于 $N$ ，继续处理下一位。
边界处理：
- 遍历结束后，如果 $N$ 本身的二进制表示中恰好有 $K$ 个 1，则答案加 1（因为前面的循环只统计了严格小于 $N$ 的数）。
- 关于 $1 \dots N$ 的范围：虽然逻辑中会统计到数字 $0$ （当 $K = 0$ 时），但题目给定 $K \geq 1$ ，而 $0$ 的二进制位中 1 的个数为 $0$ ，所以 $0$ 不会被计入答案。

Python 代码实现

python

import sys

def solve():
    # 读取输入 N 和 K
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    n = int(input_data[0])
    k = int(input_data[1])

    # 1. 预处理组合数 C(n, k)
    # N <= 10^18, 其二进制长度约为 60 层，预处理 66 层足够
    limit = 66
    c = [[0] * limit for _ in range(limit)]
    for i in range(limit):
        c[i][0] = 1
        for j in range(1, i + 1):
            c[i][j] = c[i-1][j-1] + c[i-1][j]

    # 2. 将 N 转换为二进制字符串
    s = bin(n)[2:]
    length = len(s)
    
    ans = 0
    ones_seen = 0
    
    # 3. 从高位向低位进行统计
    for i in range(length):
        if s[i] == '1':
            # 如果当前位在 N 中是 '1'
            # 我们尝试在这里填入 '0'，则构造出的数一定比 N 小
            # 剩余的可选位数
            remaining_positions = length - 1 - i
            # 还需要填入的 '1' 的数量
            needed_ones = k - ones_seen
            
            # 如果需要的 '1' 的数量在合理范围内，累加组合数
            if 0 <= needed_ones <= remaining_positions:
                ans += c[remaining_positions][needed_ones]
            
            # 填入 '1' 保持与 N 一致，继续向后看
            ones_seen += 1
            
    # 4. 判断 N 本身是否符合条件
    if ones_seen == k:
        ans += 1
        
    # 输出结果
    print(ans)

if __name__ == "__main__":
    solve()

复杂度分析

时间复杂度： $O (\log^{2} N)$ 。预处理组合数表需要 $O (\log^{2} N)$ ，遍历二进制位需要 $O (\log N)$ 。对于 $N = 10^{18}$ ， $\log_{2} N \approx 60$ ，计算量非常小。
空间复杂度： $O (\log^{2} N)$ 。主要用于存储组合数表格。

示例解析

输入 7 2：

$N = 7$ 的二进制是 111。
$i = 0$ (位 1): 选 0，后面 2 位选 2 个 1， $C (2, 2) = 1$ (即 011)。ones_seen 变为 1。
$i = 1$ (位 1): 选 0，后面 1 位选 1 个 1， $C (1, 1) = 1$ (即 101)。ones_seen 变为 2。
$i = 2$ (位 1): 选 0，后面 0 位选 0 个 1， $C (0, 0) = 1$ (即 110)。ones_seen 变为 3。
遍历结束，ones_seen (3) 不等于 $K$ (2)。
结果： $1 + 1 + 1 = 3$ 。正确。

T30212: 二进制问题 ​

T30212: 二进制问题