「一本通 6.6 例 2」2^k 进制数

形式化题目

给定正整数 $k, w$ ，记 $m = 2^k$ 。求满足下列全部条件的 $2^k$ 进制数 $r$ 的个数：

$r$ 至少是 $2$ 位数，且最高位非 $0$ ；
除最后一位外，每一位严格小于其右边相邻的那一位（即数位从左到右严格递增）；
把 $r$ 看作二进制数后总位数不超过 $w$ ，即 $r < 2^w$ 。

样例： $k=3,\ w=7$ 时 $m=8$ ，即统计「8 进制、数位严格递增、数值小于 $2^7=128$ 、至少 2 位」的数，输出 $36$ 。

正解

思路

1. 朴素做法与转化

最朴素的想法是枚举每个可能的 $r$ 逐个判断三条件——但 $r$ 最大可到 $2^w - 1$ ， $w$ 大时 $2^w$ 完全不可枚举。计数问题应转化为组合求和：按位数 $n$ 分类，固定位数后条件 2 是纯组合结构，条件 3 是数值阈值，分别处理。 $n$ 的范围：至少 $2$ 位；首位非 $0$ 意味着 $n$ 个递增数位至多从 $m-1$ 个数位里选，故 $2 \leqslant n \leqslant m-1$ 。

2. 条件 2：严格递增数位就是组合数

$n$ 位合法 $r$ （暂不考虑条件 3） $\Longleftrightarrow$ 从 $\{1, 2, \dots, m-1\}$ 中选出 $n$ 个不同的数位（选出后按升序排列即唯一确定一个 $r$ ）。因此计数为 $\binom{m-1}{n}$ 。

3. 条件 3：把 $w$ 与 $kn$ 的关系切成三档

$n$ 位 $2^k$ 进制数的取值范围是 $[\,m^{n-1},\, m^n - 1\,]$ ，对应二进制位数区间 $[\,k(n-1)+1,\, kn\,]$ 。于是对给定的 $w$ ：

全超长档 $k(n-1) \geqslant w$ ： $r \geqslant 2^{k(n-1)} \geqslant 2^w$ ，一个都不合法；且 $k(n-1)$ 随 $n$ 单调增，更大的位数同样全超长 → 枚举到此为止；
全合法档 $kn \leqslant w$ ： $r < 2^{kn} \leqslant 2^w$ ，该档全部 $\binom{m-1}{n}$ 个都合法；
临界档 $k(n-1) < w < kn$ ：同档内有合法有不合法，需要按数值细算。它至多出现在一个位数上：若 $n$ 和 $n+1$ 都是临界档，则 $w < kn$ 与 $w > kn$ 矛盾，所以临界档就是最长的那一档。

4. 临界档：只需卡首位

写 $r = d_1 \cdot 2^{k(n-1)} + \text{rest}$ ，其中 $0 \leqslant \text{rest} \leqslant 2^{k(n-1)} - 1$ ，记 $t = w - k(n-1) \geqslant 1$ ：

必要： $r < 2^w \Rightarrow d_1 \cdot 2^{k(n-1)} < 2^w \Rightarrow d_1 < 2^t$ ；
充分： $d_1 \leqslant 2^t - 1$ 时 $r \leqslant (2^t - 1) \cdot 2^{k(n-1)} + 2^{k(n-1)} - 1 = 2^w - 1 < 2^w$ 。

所以条件 3 在临界档恰等价于 $1 \leqslant d_1 \leqslant 2^t - 1$ 。固定首位后，余下 $n-1$ 位仍是从 $\{d_1+1, \dots, m-1\}$ 里任选（选法不影响上面的上界），计 $\binom{m-1-d_1}{n-1}$ ；候选不足 $n-1$ 个时组合数自然为 $0$ 。

下表按三档拆解样例 $k=3,\ w=7$ （即 $m=8$ ， $w=7$ ）的计数过程：

位数 $n$	与 $w=7$ 的关系	档位	计数方式	数量
$2$	$kn = 6 \leqslant 7$	全合法	$\binom{7}{2}$	$21$
$3$	$k(n-1) = 6 < 7 < 9 = kn$	临界	$t=1$ ，仅 $d_1=1$ ： $\binom{6}{2}$	$15$
$4$	$k(n-1) = 9 \geqslant 7$	全超长	枚举截断	$0$
合计				$36$

观察重点： $n=2$ 时所有递增数位组合都小于 $128$ ，直接用组合数； $n=3$ 是唯一的临界档，首位被阈值 $2^t = 2$ 卡在 $d_1 = 1$ ； $n=4$ 起最小值 $8^3 = 512$ 已超过 $128$ ，立即截断。三档相加 $21 + 15 = 36$ ，与样例输出一致。

最后按位数求和即得答案：

\text{ans} = \sum_{\substack{2 \leqslant n \leqslant m-1 \\ k(n-1) < w \\ kn \leqslant w}} \binom{m-1}{n} \;+\; \sum_{d_1=1}^{2^t-1} \binom{m-1-d_1}{n_0-1}

其中 $n_0$ 是临界位数（存在时）， $t = w - k(n_0-1)$ 。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35#!/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-01 00:48
# update_at: 2026-10-01 00:48

import sys
from math import comb


def count_r(k: int, w: int) -> int:
    """按位数 n 分类计数：所有满足条件的 2^k 进制数 r 的个数。"""
    m = 1 << k  # 数位集合 {0, 1, ..., 2^k - 1}，共 m 个数位
    total = 0
    for n in range(2, m):  # 至少 2 位；首位非 0，n 个递增数位至多从 m-1 个里选
        if k * (n - 1) >= w:  # r ≥ 2^{k(n-1)} ≥ 2^w，位数再增必然超长
            break
        if k * n <= w:  # r < 2^{kn} ≤ 2^w，位数不超长则每一位都合法
            total += comb(m - 1, n)  # 从 1..m-1 里选 n 个数位，严格递增唯一对应一个 r
        else:
            # 只剩首位 d1 能"救"超长：d1·2^{k(n-1)} ≤ r，故需 d1 < 2^{w-k(n-1)}；
            # 反之 d1 满足该上界时 r ≤ 2^w - 1 必然不超长，条件恰为 d1 < top。
            top = 1 << (w - k * (n - 1))
            total += sum(comb(m - 1 - d1, n - 1) for d1 in range(1, top))  # 余下 n-1 位从 d1+1..m-1 选
    return total


def solve() -> None:
    k, w = map(int, sys.stdin.read().split())
    print(count_r(k, w))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117/**
 * 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-06 00:26
 * update_at: 2026-10-06 00:26
 */
// main.cpp：「一本通 6.6 例 2」2^k 进制数
// 思路：按位数 n 分类，kn <= w 的档整档用组合数 C(m-1, n) 求和；
// 临界档（k(n-1) < w < kn）只卡首位 d1 < 2^t（t = w - k(n-1)），
// 贡献为 sum C(m-1-d1, n-1)；k(n-1) >= w 的档全超长，直接截断。
// 结果可达 200 位十进制，用 10^9 进制的大整数数组实现。

#include <cstdio>
#include <algorithm>
typedef long long ll;
using namespace std;

const ll BASE = 1000000000LL; // 大整数用 10^9 进制压位
const int MAXL = 30;          // 结果不超过 200 位十进制，30 段足够

// 全局大整数：ans 存最终答案，tmp 存每次算出的组合数（低位在前）
ll ans[MAXL];
ll tmp[MAXL];
int anslen;
int tmplen;

// 清零大整数
void big_zero(ll a[], int &len) {
    len = 1;
    a[0] = 0;
}

// ans += tmp，逐段相加处理进位
void big_add() {
    int l = max(anslen, tmplen);
    ll carry = 0;
    for (int i = 0; i < l; i++) {
        ll s = carry;
        if (i < anslen) s += ans[i];
        if (i < tmplen) s += tmp[i];
        ans[i] = s % BASE;
        carry = s / BASE;
    }
    anslen = l;
    while (carry > 0) {
        ans[anslen++] = carry % BASE;
        carry /= BASE;
    }
}

// tmp *= x（x 为小整数），逐段乘加进位
void big_mul(ll x) {
    ll carry = 0;
    for (int i = 0; i < tmplen; i++) {
        ll s = tmp[i] * x + carry;
        tmp[i] = s % BASE;
        carry = s / BASE;
    }
    while (carry > 0) {
        tmp[tmplen++] = carry % BASE;
        carry /= BASE;
    }
}

// tmp /= x（x 为小整数），高位到低位做除法
void big_div(ll x) {
    ll rem = 0;
    for (int i = tmplen - 1; i >= 0; i--) {
        ll cur = rem * BASE + tmp[i];
        tmp[i] = cur / x;
        rem = cur % x;
    }
    while (tmplen > 1 && tmp[tmplen - 1] == 0) tmplen--;
}

// 把组合数 C(N, K) 算进 tmp；利用前缀积 C(N,i) 都是整数，边乘边除不会失精度
void big_comb(ll N, ll K) {
    big_zero(tmp, tmplen);
    tmp[0] = 1;
    for (ll i = 1; i <= K; i++) {
        big_mul(N - K + i);
        big_div(i);
    }
}

int main() {
    ll k, w;
    scanf("%lld %lld", &k, &w);
    ll m = 1LL << k; // 2^k 进制，数位集合 {0,1,...,m-1}

    big_zero(ans, anslen);
    for (ll n = 2; n <= m - 1; n++) { // 位数 n：至少 2 位，至多 m-1 位
        if (k * (n - 1) >= w) break;  // r >= 2^{k(n-1)} >= 2^w，再长全超长，截断
        if (k * n <= w) {
            // 全合法档：r < 2^{kn} <= 2^w，选 n 个递增数位即唯一确定一个 r
            big_comb(m - 1, n);
            big_add();
        } else {
            // 临界档：条件 3 恰等价于首位 d1 < 2^t，t = w - k(n-1)
            ll t = w - k * (n - 1);
            ll top = 1LL << t;
            for (ll d1 = 1; d1 <= top - 1; d1++) { // 首位非 0 且小于 2^t
                ll N = m - 1 - d1; // 余下 n-1 位从 d1+1..m-1 里选
                if (N < n - 1) continue; // 候选数位不够，组合数为 0
                big_comb(N, n - 1);
                big_add();
            }
        }
    }

    // 输出：最高段不带前导 0，其余段补足 9 位
    printf("%lld", ans[anslen - 1]);
    for (int i = anslen - 2; i >= 0; i--) printf("%09lld", ans[i]);
    printf("\n");
    return 0;
}

复杂度

时间复杂度： $O(m^2)$ 次组合数运算（外层至多 $m-1 \leqslant 511$ 档位数，临界档内层至多 $2^{k-1} \leqslant 256$ 个首位），每次 math.comb 为 $O(n)$ ，整体远小于 1000ms 限制。
空间复杂度： $O(1)$ 工作变量；结果不超过 200 位十进制（约 664 bit），Python 原生大整数直接承载。

总结

「数位严格递增、首位非 $0$ 」的计数标准手法是组合数：选集合即定序列，答案为 $\binom{m-1}{n}$ 。
二进制位数约束要翻译成数值约束 $r < 2^w$ ，再按 $kn$ 与 $w$ 的关系分「全超长 / 全合法 / 临界」三档；全超长档给出枚举的天然上界，全合法档可以整档打包求和。
临界档用「夹逼」证明： $r = d_1 \cdot 2^{k(n-1)} + \text{rest}$ 的上下界说明超长与否只取决于首位 $d_1$ 是否小于 $2^{w-k(n-1)}$ ，把一个数值判断化回了组合计数。