[NOIP2006-提高] 2^k进制数

形式化题目

给定正整数 $k$ （ $1 \leqslant k \leqslant 9$ ）与 $w$ （ $k < w$ ），记基数 $B = 2^k$ 。统计满足下列全部条件的 $B$ 进制数 $r$ 的个数：

$r$ 至少是个 2 位数；
从左到右每一位严格小于右边相邻的一位，且最高位不为 $0$ ；
把 $r$ 看成二进制数时，总位数不超过 $w$ （即 $r < 2^w$ ）。

题面用“把长度 $w$ 的 01 串从右起每 $k$ 位一段划分”来解释第 3 条：不足 $k$ 位的段在最左边，段数即位数 $m$ 。这只是等价说法，本质约束就是 $r < 2^w$ 。

样例：输入 3 7，输出 36。按 $k=3, w=7$ （八进制）手工展开：

2 位数：最高位为 1 时低位可取 $2 \sim 7$ 共 $6$ 个（ $12,13,\dots,17$ ），最高位为 2 时 $5$ 个，……，最高位为 6 时 $1$ 个（ $67$ ），共 $6+5+\dots+1 = 21$ 个。
3 位数：低位两段占 $2k = 6$ 个二进制位，再加上最高位 $d_1$ 自己的位数，总长不能超过 $7$ ，故 $d_1$ 只能占 $1$ 位即 $d_1 = 1$ （长度公式的完整推导见下文正解）；第二位为 2 时第三位可取 $3 \sim 7$ 共 5 个（ $123,124,\dots,127$ ），为 3 时 4 个，……，为 6 时 1 个（ $167$ ），共 $5+4+\dots+1 = 15$ 个。
4 位数：仅低位就要 $3k = 9$ 位，加上最高位至少 1 位即 $\geqslant 10 > 7$ ，不可能，故答案 $21 + 15 = 36$ 。

正解

思路

朴素做法及其瓶颈。 最直接的思路是枚举所有长度 $m \geqslant 2$ 的严格递增数字序列，逐个换算成二进制检查长度。但这样的序列共有 $\sum_{m \geqslant 2} \binom{B-1}{m} = 2^{B-1} - B$ 个， $k=9$ 时约为 $10^{153}$ ；等价地枚举所有长度不超过 $w$ 的 01 串也是指数级。瓶颈在于把"长度检查"放在了最内层。

关键观察：长度只由位数和最高位决定。 设 $r$ 的各位为 $d_1 d_2 \dots d_m$ （ $d_1$ 是最高位），则

r = d_1 \cdot B^{\,m-1} + \underbrace{(d_2 \cdots d_m \text{ 组成的部分})}_{<\, B^{\,m-1} = 2^{k(m-1)}}.

后半部分只占据低 $k(m-1)$ 个二进制位，而 $d_1 \geqslant 1$ ，所以

\text{bitlen}(r) = k(m-1) + \text{bitlen}(d_1).

也就是说，长度条件 $k(m-1) + \text{bitlen}(d_1) \leqslant w$ 只跟 $(m, d_1)$ 有关，与其余各位取值无关。这立刻给出位数上界 $m_{\max} = \min\!\big(B-1,\ \lfloor (w-1)/k \rfloor + 1\big)$ （最高位至少占 1 位）。

固定 $(m, a)$ 后是纯组合。 最高位取 $a$ 时，其余 $m-1$ 位必须从 $\{a+1, \dots, B-1\}$ 中选出，递增顺序唯一确定，共 $\binom{B-1-a}{m-1}$ 种。

按最高位的位数分段求和。 长度条件对同一位数 $j = \text{bitlen}(a)$ 的 $a$ 是一样的，故把 $a$ 按 $[2^{j-1}, 2^j-1]$ 分段。段内用 hockey-stick 恒等式 $\sum_{i=r}^{n} \binom{i}{r} = \binom{n+1}{r+1}$ （令 $t = B-1-a$ ）：

\sum_{a=2^{j-1}}^{2^{j}-1} \binom{B-1-a}{m-1} = \binom{B-2^{j-1}}{m} - \binom{B-2^{j}}{m},

其中约定 $\binom{n}{m} = 0$ 当 $n < m$ 。最终答案为

\text{ans} = \sum_{m=2}^{m_{\max}} \ \sum_{j=1}^{\min(k,\ w-k(m-1))} \left[\binom{B-2^{j-1}}{m} - \binom{B-2^{j}}{m}\right].

把样例 $k=3, w=7$ （ $B=8$ ）按这个二维求和逐格展开：

$m$	$j$ （最高位 $a$ ）	长度 $3(m-1)+j$	是否 $\leqslant 7$	该格贡献 $\binom{8-2^{j-1}}{m} - \binom{8-2^{j}}{m}$
2	1（ $a=1$ ）	4	✓	$\binom{7}{2} - \binom{6}{2} = 6$
2	2（ $a=2,3$ ）	5	✓	$\binom{6}{2} - \binom{4}{2} = 9$
2	3（ $a=4\sim7$ ）	6	✓	$\binom{4}{2} - \binom{0}{2} = 6$
3	1（ $a=1$ ）	7	✓	$\binom{7}{3} - \binom{6}{3} = 15$
3	2（ $a=2,3$ ）	8	✗	不计
4	—	$\geqslant 10$	✗	不存在 4 位数

观察重点：表格第一行（ $m=2, j=1$ ）的 $6$ 正是题面"最高位为 1 有 6 个"， $j=2$ 格把"最高位为 2 的 5 个 + 为 3 的 4 个"打包成 $9$ ， $j=3$ 格打包成 $6$ ，三段合计 $21$ ； $m=3$ 只剩 $j=1$ （最高位必须是 $1$ ）贡献 $15$ 。逐格相加 $6+9+6+15 = 36$ ，与样例完全一致——分段求和没有漏掉任何一种分组，也不必逐个枚举数字。

代码

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/**
 * 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-10 11:30
 * update_at: 2026-10-10 11:30
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// 十进制大整数（little-endian），只做 3551 需要的加法/减法/乘法/整除小整数
struct BigInt {
    vector<int> d;
    BigInt() { d.push_back(0); }
    BigInt(ll x) { d.clear(); if (x == 0) d.push_back(0); else while (x) { d.push_back((int)(x % 10)); x /= 10; } }
    void trim() { while (d.size() > 1 && d.back() == 0) d.pop_back(); }
    bool is_zero() const { return d.size() == 1 && d[0] == 0; }
    int cmp(const BigInt& o) const {
        if (d.size() != o.d.size()) return d.size() < o.d.size() ? -1 : 1;
        for (int i = (int)d.size() - 1; i >= 0; i--)
            if (d[i] != o.d[i]) return d[i] < o.d[i] ? -1 : 1;
        return 0;
    }
    string str() const { string r; for (int i = (int)d.size() - 1; i >= 0; i--) r += char('0' + d[i]); return r; }
    BigInt operator+(const BigInt& o) const {
        BigInt r; r.d.assign(max(d.size(), o.d.size()) + 1, 0);
        for (size_t i = 0; i < d.size(); i++) r.d[i] += d[i];
        for (size_t i = 0; i < o.d.size(); i++) r.d[i] += o.d[i];
        for (size_t i = 0; i + 1 < r.d.size(); i++) { r.d[i + 1] += r.d[i] / 10; r.d[i] %= 10; }
        r.trim(); return r;
    }
    BigInt operator-(const BigInt& o) const {   // 假设 *this >= o
        BigInt r; r.d = d;
        for (size_t i = 0; i < o.d.size(); i++) {
            r.d[i] -= o.d[i];
            if (r.d[i] < 0) { r.d[i] += 10; r.d[i + 1]--; }
        }
        for (size_t i = 0; i + 1 < r.d.size(); i++)
            if (r.d[i] < 0) { r.d[i] += 10; r.d[i + 1]--; }
        r.trim(); return r;
    }
    BigInt operator*(const BigInt& o) const {
        BigInt r; r.d.assign(d.size() + o.d.size(), 0);
        for (size_t i = 0; i < d.size(); i++)
            for (size_t j = 0; j < o.d.size(); j++)
                r.d[i + j] += d[i] * o.d[j];
        for (size_t i = 0; i + 1 < r.d.size(); i++) { r.d[i + 1] += r.d[i] / 10; r.d[i] %= 10; }
        r.trim(); return r;
    }
    BigInt div_small(ll x) const {
        BigInt r; r.d.assign(d.size(), 0);
        ll rem = 0;
        for (int i = (int)d.size() - 1; i >= 0; i--) {
            ll cur = rem * 10 + d[i];
            r.d[i] = (int)(cur / x); rem = cur % x;
        }
        r.trim(); return r;
    }
};

// 组合数 C(n, k)，结果用 BigInt
BigInt C[520][520];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int k, w;
    cin >> k >> w;
    int B = 1 << k;

    // 组合数打表
    for (int i = 0; i <= B; i++) {
        C[i][0] = BigInt(1);
        for (int j = 1; j <= i; j++)
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
    }

    // 位数 m 的上界
    int m_max = min(B - 1, (w - 1) / k + 1);
    BigInt ans(0);
    for (int m = 2; m <= m_max; m++) {
        for (int j = 1; j <= min(k, w - k * (m - 1)); j++) {
            // C(B - 2^(j-1), m) - C(B - 2^j, m)
            BigInt a = C[B - (1 << (j - 1))][m];
            BigInt b = C[B - (1 << j)][m];
            ans = ans + (a - b);
        }
    }
    cout << ans.str() << "\n";
    return 0;
}

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
36
37
38
39#!/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-02 07:05
# update_at: 2026-10-02 07:05

import sys
from math import comb


def count_rising(k: int, w: int) -> int:
    """数出二进制长度不超过 w 的、2^k 进制下位数严格递增且至少两位的数的个数。

    r 有 m 位（最高位为 a）时，二进制长度 = k*(m-1) + a 的位数，因为 r 的最高位
    就是最高位数字 a 所占的那 k 位里的最高有效位。

    固定 m 与最高位 a：其余 m-1 位必须从比 a 大的数字 {a+1..B-1} 里选，共
    C(B-1-a, m-1) 种。按 a 的位数 j 分段（a 落在 [2^(j-1), 2^j-1]），对
    C(B-1-a, m-1) 用 hockey-stick 公式求和即 C(B-2^(j-1), m) - C(B-2^j, m)。
    """
    B = 1 << k  # 2^k 进制的基数
    # 位数 m 的上界：k*(m-1) 位加上最高位至少 1 位不得超过 w；数字取自 1..B-1 故 m<=B-1
    m_max = min(B - 1, (w - 1) // k + 1)
    return sum(
        comb(B - (1 << (j - 1)), m) - comb(B - (1 << j), m)  # 最高位落在 [2^(j-1), 2^j-1]
        for m in range(2, m_max + 1)
        for j in range(1, min(k, w - k * (m - 1)) + 1)       # 长度约束：k*(m-1)+j <= w
    )


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    k, w = next(data), next(data)
    print(count_rising(k, w))


if __name__ == "__main__":
    solve()

复杂度

位数 $m$ 至多 $B-1 \leqslant 511$ 种，最高位位数 $j$ 至多 $k \leqslant 9$ 种，每格一次 math.comb（参数不超过 $512$ 的小整数运算），总时间 $O(2^k \cdot k)$ ，约 $5 \times 10^3$ 次组合数计算；额外空间 $O(1)$ ，答案用 Python 内置大整数精确表示（题面保证不超过 200 位）。1 s 限制内实测每个用例约 $0.02$ s。

总结

先定位长度条件的自由度： $\text{bitlen}(r) = k(m-1) + \text{bitlen}(d_1)$ ，把指数级的"逐序列验证"降维成对 $(m, d_1)$ 的二维求和，这是本题从暴力到正解的全部关键。
递增序列 = 子集：固定最高位后低位只是"从更大的数里选 $m-1$ 个"，是纯组合数；再按最高位的二进制位数分段，hockey-stick 恒等式把段内求和化成两个组合数之差。
边界由约定自然吸收：range(2, ...) 保证至少两位， $j$ 从 1 开始保证最高位非 0，内层上限 $\leqslant 0$ 时该位数整段跳过，math.comb 对 $n < m$ 返回 0。
复杂度 $O(2^k k)$ 与最优解同阶；结果可能很大但不超过 200 位，Python 大整数直接输出十进制即可。

[NOIP2006-提高] 2^k进制数

目录

形式化题目

正解

思路

代码

复杂度

总结