用 f(n)=#{j<n: popcount(j)=k-1} 把合法 n 压成一段连续区间,位贪心求第 m 个候选数,O(log n) 得最小 n 与解的个数。
OJ: roj
题目 ID: 1777
难度:提高
标签:位运算组合数学贪心python
创建: 2026-10-08 01:55
更新: 2026-10-08 01:55
形式化题目
给定
记
那么每组询问就是一个方程:
题面保证 2 1。
数据来源说明
本题与 Codeforces 431D Random Task 同源(题面逐字对应)。
但 data.py 现场生成,本仓库的 std.cpp 也出自同一次整理,
并非官方数据;额外追问的「解的个数」一项更是原题所无(原题只要求输出一个 std.cpp,结论已用暴力枚举在
正解
思路
朴素做法。 从
关键恒等式。 把
而
(最后一步因为
这一步把「区间计数」变成了「排名」:
则
| 合法 |
最小 |
解的个数 | |
|---|---|---|---|
这也顺带解释了为什么解一定是「连续一段」而不是零散分布——因为
特例 1 -1。
求第 used」。在第 need = p - used 个
- 若
,目标落在这支里,本位取 ; - 否则减去这一支的方案数,本位取
、 used加一。
扫完 64 位得到的就是
以样例 2 1,与样例一致。
无解的处理。 题面保证 0 0 兜底。
代码
Python 版:
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 01:55
# update_at: 2026-10-08 01:55
import sys
from math import comb
BITS = 64 # n 的二进制位数上界:题目要求输出的 n 落在 [1, 2^64 - 1]
def kth_number(rank: int, ones: int) -> int:
"""第 rank 小(rank 从 1 起)的「二进制恰有 ones 个 1」的非负整数。"""
x = 0
used = 0
for i in range(BITS - 1, -1, -1):
# 本位取 0 时,低位 i 位里还要凑出 need 个 1,方案数为 C(i, need)
need = ones - used
ways = comb(i, need) if 0 <= need <= i else 0
if rank > ways: # 目标不在「本位取 0」这一支里,本位必须取 1
rank -= ways
x |= 1 << i
used += 1
if used == ones:
break # 1 已放满,低位全填 0
return x
def answer(m: int, k: int) -> tuple[int, int]:
"""f(n) = m 时的 (最小 n, 解的个数);个数 -1 表示无穷多。
恒等式 f(n) = #{ j < n : popcount(j) = k-1 } 把 n 的取值压成一段连续区间:
m >= 1 时是 [a_{m-1}+1, a_m](a_i 为第 i+1 个候选),m == 0 时是 [1, 2^(k-1)-1]。
"""
if k == 1:
return (1, -1) if m == 1 else (0, 0) # 候选只有 j = 0,f 恒为 1
p = k - 1
if m == 0:
return 1, (1 << p) - 1
if comb(BITS, p) < m + 1:
return 0, 0 # 2^64 内凑不出 m+1 个候选,题面保证不会出现
low = kth_number(m, p) # a_{m-1}
high = kth_number(m + 1, p) # a_m
return low + 1, high - low
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
t = next(data)
out: list[str] = []
for _ in range(t):
m, k = next(data), next(data)
first, count = answer(m, k)
out.append(f"{first} {count}")
print('\n'.join(out))
if __name__ == "__main__":
solve()C++ 版(同一算法):
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-08 01:55
* update_at: 2026-10-08 01:55
*/
// 1777《寻找整数》:给定 m, k,求正整数 n 使 (n, 2n] 中恰有 m 个数二进制含 k 个 1。
//
// 关键恒等式(本解的全部依据):
// f(n) = #{ x : n < x <= 2n 且 popcount(x) = k }
// = #{ j : 0 <= j <= n-1 且 popcount(j) = k-1 }。
// 推导:把 (n, 2n] 拆成偶数与奇数。偶数 x = 2y (y <= n) 的 popcount 等于 popcount(y);
// 奇数 x = 2y+1 的 popcount 等于 popcount(y)+1,且 2y+1 <= 2n 等价于 y <= n-1。
// 于是偶数部分的贡献正是 f(n) 里的「popcount(y) = k」那半边,与 #{(0,n] 中 popcount=k}
// 逐项抵消,只剩奇数部分 #{(0,n) 中 popcount = k-1},即上面的恒等式。
// 所以 f(n) = m 等价于「恰有 m 个 popcount 为 k-1 的非负整数严格小于 n」。
// 设 a_i 是第 i+1 小(下标 0 起)的「popcount = p」的整数(p = k-1),则
// m >= 1:n 的取值恰为闭区间 [a_{m-1}+1, a_m],最小 n = a_{m-1}+1,解的个数 = a_m - a_{m-1};
// m == 0:n 的取值恰为 [1, a_0] = [1, 2^p - 1],最小 n = 1,个数 = 2^p - 1;
// k == 1:p = 0 时只有 j = 0 一个候选,f(n) 恒等于 1,故 m = 1 有无穷多解(个数记 -1)。
// a_i 用「按二进制位从高到低贪心」求出:本位取 0 时低位有 C(i, 剩余个数) 种填法,
// 与 rank 比较即可决定本位取 0 还是取 1,一次 O(64)。
//
// 复杂度:预处理组合数 O(64^2);每组询问 2 次 O(64) 贪心 → 单组 O(log n)。
// t <= 2000 时总计约 2.6e5 次基本运算。空间 O(64^2)。
// 数值范围:n 至多 2^64-1,组合数最大 C(64,32) ≈ 1.83e18,全部用 unsigned long long。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull; // 答案 n 允许取到 2^64-1,超出 ll 上界,必须用无符号
const int BITS = 64; // 二进制位数上界:题目要求输出的 n 落在 [1, 2^64 - 1]
ull binom[BITS + 1][BITS + 1]; // binom[i][j] = 组合数 C(i, j),j > i 处保持 0
// 组合数表:数位贪心与无解判定都要反复查,直接按杨辉三角打表
void init_binom() {
for (int i = 0; i <= BITS; i++) {
binom[i][0] = 1;
for (int j = 1; j <= i; j++) {
binom[i][j] = binom[i - 1][j - 1] + binom[i - 1][j];
}
}
}
// 第 rank 小(rank 从 1 起)的「二进制恰有 ones 个 1」的非负整数
ull kth_number(ull rank, int ones) {
ull x = 0;
int used = 0;
for (int i = BITS - 1; i >= 0; i--) {
// 本位取 0,低位 i 位里还要凑出 need 个 1,方案数就是 C(i, need)
int need = ones - used;
ull ways = (need >= 0 && need <= i) ? binom[i][need] : 0ULL;
if (rank > ways) { // 第 rank 个不在「本位取 0」这一支里
rank -= ways;
x |= 1ULL << i;
used++;
}
if (used == ones) break; // 1 已经放满,低位全填 0
}
return x;
}
int main() {
init_binom();
int t;
if (scanf("%d", &t) != 1) return 0;
while (t--) {
ull m;
int k;
if (scanf("%llu %d", &m, &k) != 2) break;
if (k == 1) { // 候选只剩 j = 0,f(n) 恒为 1
if (m == 1) printf("1 -1\n");
else printf("0 0\n"); // 题面保证 10^18 内不会出现
continue;
}
int p = k - 1; // 只需数「popcount = p 且严格小于 n」的整数个数
if (m == 0) {
// n 取遍 [1, 2^p - 1],最小 n 是 1,个数 2^p - 1
printf("1 %llu\n", (1ULL << p) - 1);
continue;
}
if (binom[BITS][p] < m + 1) { // 2^64 内根本凑不出 m+1 个候选,无解
printf("0 0\n");
continue;
}
ull prev_big = kth_number(m, p); // a_{m-1}
ull next_big = kth_number(m + 1, p); // a_m
printf("%llu %llu\n", prev_big + 1, next_big - prev_big);
}
return 0;
}复杂度
- 时间:C++ 版预处理组合数表
,每组询问两次按位贪心各 , 故单组 ,总计 ;Python 版省掉建表、 每次现调 math.comb,仍是每组的量级,复杂度同阶。 时约 次基本运算,实测远低于 1000 ms 限时。 注意本解法完全不依赖 的大小—— 只作为「第几名」参与组合数比较, 所以 取到 与取到 的代价完全相同。 - 空间:组合数表
, ,常数量级。 - 数值范围:答案
允许取到 ,超出 long long上界, 故 C++ 里用unsigned long long;组合数最大为, 同样在无符号 64 位内不溢出。Python 侧整数无上界,不需要额外处理。
总结
- (1) 式是本题的全部内容:
。 它的证明只用了一条性质——左移一位不改变 的个数, 这条性质让区间的「一进一出」精确抵消掉一半,剩下的半边恰好是 的排名。 - 从「区间计数」转向「排名」:一旦看出
, 单调性与连续性就是显然的( 每次只涨 或 ), 解的集合也必然是一段连续区间 。 - 数位贪心求第
小:判断「第 个候选在哪一支」时, 低位自由位的方案数恰好是组合数 , 于是每个询问只需从高到低扫 64 位。这类「组合数进制」贪心 在「第 小的二进制含 个 的数」「字典序第 小」等问题上可复用。 - 特例要单独想:
时 是常函数 ,二分或贪心都不会自然报错, 必须在入口处特判,否则「最大合法 」会一路跑到 之外。