「一本通 5.3 例 1」Amount of Degrees

形式化题目

给定区间 $[X, Y]$ 与参数 $K, B$ ，统计其中满足下述条件的整数 $n$ 的个数：

n = B^{e_1} + B^{e_2} + \dots + B^{e_K}, \qquad 0 \leqslant e_1 < e_2 < \dots < e_K

即 $n$ 恰好等于 $K$ 个互不相等的 $B$ 的非负整数次幂之和。例如 $X=15,\ Y=20,\ K=2,\ B=2$ 时， $17 = 2^4+2^0$ 、 $18 = 2^4+2^1$ 、 $20 = 2^4+2^2$ 满足条件，答案为 $3$ 。

正解

思路

1. 等价转化：幂之和就是 $B$ 进制的 0/1 数

$B$ 进制表示是唯一的。若 $n = B^{e_1} + \dots + B^{e_K}$ 且指数互不相同，把这些幂按数位直接摆放不会产生任何进位，得到的 $B$ 进制表示就是"只有 $K$ 个 $1$ 、其余位为 $0$ "；反之，一个 $B$ 进制只含 $0/1$ 的数，把每个 $1$ 还原成对应的幂即得所需拆分。因此：

n \text{ 满足条件} \iff n \text{ 的 } B \text{ 进制表示只含 } 0/1 \text{ 且恰有 } K \text{ 个 } 1

（指数只取非负整数：样例含 $2^0$ ，若允许负指数会得到分数，与"统计整数"矛盾。）

2. 朴素做法与瓶颈

最直接的做法是枚举 $[X, Y]$ 中每个数、转成 $B$ 进制检查一遍——单次判断只要 $\mathcal{O}(\log_B Y)$ ，但 $Y - X$ 最大可达 $2^{31}-1$ ，整体不可行。瓶颈在区间跨度而不在单次判断，于是改用前缀和：令 $f(n)$ 统计 $[0, n]$ 中的合法数，答案 $= f(Y) - f(X-1)$ ，区间长度从复杂度里消失，问题变成单点计数 $f(n)$ 。

3. $f(n)$ ：从高位卡上界，一松绑就用组合数收账

$f(n)$ 是"上界限制 + 逐位决策"结构，即数位 DP。把 $n$ 写成 $B$ 进制，从高位到低位扫描，维护：

ones：已确定的高位里 $1$ 的个数（还缺 $K - \texttt{ones}$ 个）；
rest：当前位之后还剩多少个低位。

一旦某一位严格小于 $n$ ，上界就永久松绑，低位可以自由选 $0/1$ ，方案数恰是"从剩余位里挑够其余的 $1$ "的组合数，可以立刻入账而不必继续递归：

当前位数字 $d$	决策与入账
$d \geqslant 2$	本位放 $0$ 或 $1$ 都严格小于 $n$ ，本位加低位共 $\texttt{rest}+1$ 位全自由，入账 $\dbinom{\texttt{rest}+1}{K-\texttt{ones}}$ ，扫描结束
$d = 1$	放 $0$ 则低于上界，入账 $\dbinom{\texttt{rest}}{K-\texttt{ones}}$ ；放 $1$ 继续卡上界，`ones` 加 1
$d = 0$	放 $1$ 会超过 $n$ ，只能放 $0$ 继续卡上界，入账 $0$

扫完全部位后， $n$ 本身每一位都是 $0/1$ ，若 $\texttt{ones} = K$ 再补上这 $1$ 个方案。所有入账项对应"第一次变小的位置不同"的互斥集合，因此不重不漏。边界上， $n=0$ 时数字列为 $[0]$ 、全程无入账，故 $X=1$ 对应的 $f(0)=0$ ； $K$ 超过可凑位数时组合数越界取 $0$ ，不会多计。

4. 样例推演

对 $f(20)$ （ $K=2,\ B=2,\ 20 = 10100_2$ ）逐位执行上表：

当前位（权值）	$d$	操作	本步入账	累计	`ones`
$2^4$	$1$	放 $0$ 账 $\binom{4}{2}$ ，放 $1$ 继续	$6$	$6$	$1$
$2^3$	$0$	只能放 $0$	$0$	$6$	$1$
$2^2$	$1$	放 $0$ 账 $\binom{2}{1}$ ，放 $1$ 继续	$2$	$8$	$2$
$2^1$	$0$	只能放 $0$	$0$	$8$	$2$
$2^0$	$0$	只能放 $0$	$0$	$8$	$2$
扫完	—	$\texttt{ones}=2=K$ ， $20$ 本身入账	$1$	$9$	$2$

其中"放 $0$ 账 $\binom{4}{2}=6$ "数出的是 $16$ 以下恰含两个 $1$ 的数： $3,5,6,9,10,12$ ；"放 $0$ 账 $\binom{2}{1}=2$ "数出的是 $10010_2=18$ 、 $10001_2=17$ 。同理 $f(14)$ （ $14 = 1110_2$ ）依次入账 $\binom{3}{2} + \binom{2}{1} + \binom{1}{0} = 6$ ，扫完 $\texttt{ones} = 3 \neq 2$ 不补，故 $f(14) = 6$ 。最终答案 $f(20) - f(14) = 9 - 6 = 3$ ，对应 $17, 18, 20$ ，与题面样例一致。

代码

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59#!/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-09-30 20:16
# update_at: 2026-09-30 20:16

import sys
from functools import cache


@cache
def comb(n: int, k: int) -> int:
    """C(n, k)，越界取 0：数位 DP 展开成组合数时的查表。"""
    if k < 0 or k > n:
        return 0
    if n == 0 or k == 0:
        return 1
    return comb(n - 1, k - 1) + comb(n - 1, k)


def to_base(n: int, b: int) -> list[int]:
    """n 的 b 进制数字，高位在前；n = 0 时返回 [0]。"""
    digits: list[int] = []
    while n:
        digits.append(n % b)
        n //= b
    return digits[::-1] or [0]


def count(n: int, k: int, b: int) -> int:
    """[0, n] 中 b 进制表示只含 0/1 且恰有 k 个 1 的数的个数。

    从高位到低位卡上界：当前位数字 > 1 时，本位放 0/1 都严格小于 n，
    低位可任选 0/1，直接用组合数收尾；当前位是 1 时，放 0 同样低于上界
    （组合数入账），放 1 继续卡；当前位是 0 时只有放 0 才不越界。
    """
    digits = to_base(n, b)
    ans = 0
    ones = 0  # 已确定的高位里 1 的个数
    for i, d in enumerate(digits):
        rest = len(digits) - i - 1  # 当前位之后还剩多少个低位
        if d > 1:
            # 本位放 0 或 1 都小于 n：从「本位 + 低位」共 rest+1 位里再挑 k-ones 个 1
            return ans + comb(rest + 1, k - ones)
        if d == 1:
            ans += comb(rest, k - ones)  # 本位放 0，rest 个低位自由选 0/1
            ones += 1                    # 本位放 1，继续卡上界
        # d == 0：放 1 会超过 n，只能放 0 继续卡
    return ans + (ones == k)  # n 本身每一位都是 0/1，看它是否恰好 k 个 1


def solve() -> None:
    x, y, k, b = map(int, sys.stdin.buffer.read().split())
    print(count(y, k, b) - count(x - 1, k, b))


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/**
 * 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-05 10:38
 * update_at: 2026-10-05 10:38
 */
#include <iostream>
using namespace std;

typedef long long ll;

const int MAXN = 45; // B=2 时 2^31-1 只有 31 位，组合数参数留出余量

ll comb_table[MAXN][MAXN]; // comb_table[n][k] = C(n, k)
ll digits[MAXN];           // n 的 B 进制数字，高位在前，下标从 0 开始
int digit_cnt;             // digits 中有效位数的个数

// 预处理帕斯卡三角，供数位扫描时查组合数。
void build_comb() {
    for (int n = 0; n < MAXN; n++) {
        comb_table[n][0] = 1;
        for (int k = 1; k <= n; k++) {
            comb_table[n][k] = comb_table[n - 1][k - 1] + comb_table[n - 1][k];
        }
    }
}

// 返回 C(n, k)；k < 0 或 k > n 时按 0 处理（凑不够 1 的方案不存在）。
ll comb(ll n, ll k) {
    if (k < 0 || k > n) {
        return 0;
    }
    return comb_table[n][k];
}

// 把 n 写成 b 进制，高位在前存入 digits[]；n = 0 时存入单个 0。
void to_base(ll n, ll b) {
    digit_cnt = 0;
    if (n == 0) {
        digits[digit_cnt] = 0;
        digit_cnt++;
        return;
    }
    ll low[MAXN];
    int low_cnt = 0;
    while (n > 0) {
        low[low_cnt] = n % b;
        low_cnt++;
        n /= b;
    }
    for (int i = low_cnt - 1; i >= 0; i--) {
        digits[digit_cnt] = low[i];
        digit_cnt++;
    }
}

// 统计 [0, n] 中 B 进制表示只含 0/1 且恰有 k 个 1 的数的个数。
// 从高位到低位卡上界：某一位一旦严格小于 n，剩余位可自由选 0/1，用组合数一次收账。
ll count_prefix(ll n, ll k, ll b) {
    to_base(n, b);
    ll ans = 0;
    ll ones = 0; // 已确定的高位中 1 的个数，还差 k - ones 个
    for (int i = 0; i < digit_cnt; i++) {
        ll d = digits[i];
        ll rest = digit_cnt - i - 1; // 当前位之后还剩多少个低位
        if (d > 1) {
            // 本位放 0 或 1 都严格小于 n，本位加低位共 rest+1 位自由挑 k-ones 个 1
            return ans + comb(rest + 1, k - ones);
        }
        if (d == 1) {
            ans += comb(rest, k - ones); // 本位放 0，rest 个低位自由选
            ones++;                      // 本位放 1，继续卡上界
        }
        // d == 0：放 1 会超过 n，只能放 0 继续卡上界，不入账
    }
    if (ones == k) {
        ans++; // n 本身每位都是 0/1，看它是否恰好 k 个 1
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll x, y, k, b;
    cin >> x >> y;
    cin >> k >> b;

    build_comb();
    cout << count_prefix(y, k, b) - count_prefix(x - 1, k, b) << "\n";

    return 0;
}

复杂度

时间复杂度： $\mathcal{O}(\log_B Y)$ 次组合数查询。 $n$ 的 $B$ 进制表示最多 $31$ 位（ $B=2$ 且 $Y = 2^{31}-1$ ），每位至多入账一次；组合数用 functools.cache 记忆化的帕斯卡递归，comb(n, k) 的参数范围是 $n \leqslant 31$ 、 $k \leqslant 20$ ，缓存的子问题总量不超过 $32 \times 21$ ，均摊为常数。
空间复杂度： $\mathcal{O}(\log_B Y)$ 。除数字数组与组合数缓存外只有常数个变量，实测峰值约 $14.7\text{ MB}$ （主要是 Python 解释器本身），相对 $128\text{ MB}$ 限制可忽略。

总结

本题的钥匙是一次等价转化：" $K$ 个互不相等的 $B$ 的幂之和"就是" $B$ 进制只含 $0/1$ 且恰有 $K$ 个 $1$ 的数"，唯一性由 $B$ 进制表示唯一保证。

区间计数先用前缀相减消掉跨度，再把单点计数 $f(n)$ 写成数位 DP 的组合数展开：从高位到低位卡上界，每位只有三种决策，一旦严格小于上界就用 $\binom{\texttt{rest}}{K-\texttt{ones}}$ 一次性收账。这样状态量被压成线性扫描， $\mathcal{O}(\log_B Y)$ 完成整个计算；同一算法在 C++ 里既可以写成 f[pos][ones][tight] 的递归数位 DP，也可以照本解法写成逐位累加的迭代形式，复杂度相同。