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 构成的边界数）。

T30212: 二进制问题 ​

T30212: 二进制问题