P1066 2^k进制数

题目描述

设 (r) 是个 (2^k) 进制数，并满足以下条件：

(r) 至少是个 2 位的 (2^k) 进制数。
作为 (2^k) 进制数，除最后一位外，(r) 的每一位严格小于它右边相邻的那一位。
将 (r) 转换为二进制数 (q) 后，则 (q) 的总位数不超过 (w)。

在这里，正整数 (k, w) 是事先给定的。问：满足上述条件的不同的 (r) 共有多少个？

再换一种角度理解：设 (S) 是长度为 (w) 的 01 字符串，将 (S) 从右起划分为若干个长度为 (k) 的段，每段对应一位 (2^k) 进制的数，如果 (S) 至少可分成 2 段，且这些段对应的 (2^k) 进制位严格递增，则 (S) 对应一个满足条件的 (r)。

读题分析

这道题表面上是在数「有多少个满足条件的数」，但约束条件其实把它变成了一个纯粹的组合计数问题。

三个条件的含义：

至少 2 位：排除单数字的情况。
严格递增：(r) 的各位数字从左到右严格递增。这意味着一旦确定了「选哪些数字」，它们的排列顺序是唯一确定的（从小到大）。
二进制不超过 (w) 位：决定了 (r) 作为 (2^k) 进制数最多能有多少位。

核心观察

「严格递增」+「数字不重复」=「选数即确定」。

如果 (r) 有 (m) 位，且各位从 1 到 (2^k-1) 中选出并严格递增，那么有多少种可能的 (r)？答案就是从 (2^k-1) 个候选数字中选 (m) 个的组合数。

这大大简化了问题——我们不再需要枚举具体的排列，只需要计算组合数。

算法分析

设：

(max = 2^k - 1)：(2^k) 进制下每一位的最大值（注意不能取 (2^k)，那会进位）
(len = w / k)：完整的位数（整除）
(p = w % k)：最高位剩余的二进制位数

情况 1：位数为 2 到 (len) 的数

对于恰好 (m) 位（(2 \le m \le len)）的情况：

每一位从 1 到 (2^k-1) 中选，选 (m) 个，严格递增排列只有一种方式。

种数为：(C(2^k-1, m))

累加所有可能的位数：

Σ_m=2…len C(2^k−1, m)

情况 2：位数为 (len+1) 的数（仅当 (p > 0) 时存在）

当 (w) 不能被 (k) 整除时，(r) 最多可以有 (len+1) 位。此时最高位（最左）对应 (p) 个二进制位，所以最高位的取值范围是 ([1, 2^p-1])（不能为 0，因为那是最高位且至少 2 位）。

设最高位为 (i)（(1 \le i \le 2^p-1)），剩下的 (len) 位必须：

从大于 (i) 的数字中选（严格大于 (i)）
选 (len) 个，严格递增

种数为：(C(2^k-1-i, len))

累加所有可能的最高位值：

Σ_{i=1…2^p−1} C(2^k−1−i, len)

最终答案

第一种情况累加：Σ_m=2…len C(2^k−1, m)

第二种情况（仅当 (p > 0)）累加：Σ_{i=1…2^p−1} C(2^k−1−i, len)

两部分之和即为答案。

高精度问题

(k \le 15)，(w \le 200000)，组合数的值会非常大，远超 long long 范围。必须实现高精度加法和高精度组合数计算。

代码实现

C++ 高精度实现

#include <bits/stdc++.h>
using namespace std;

const int B = 1000000000; // 压 9 位
typedef vector<long long> BigInt;

BigInt add(const BigInt& a, const BigInt& b) {
    BigInt c;
    int n = max(a.size(), b.size()), carry = 0;
    for (int i = 0; i < n || carry; i++) {
        long long s = carry;
        if (i < (int)a.size()) s += a[i];
        if (i < (int)b.size()) s += b[i];
        c.push_back(s % B);
        carry = s / B;
    }
    return c;
}

// C(n, m) 高精度计算
BigInt C(int n, int m) {
    if (m < 0 || m > n) return BigInt();
    if (m == 0 || m == n) return BigInt{1};
    if (m > n / 2) m = n - m;
    
    BigInt res{1};
    for (int i = 1; i <= m; i++) {
        // res = res * (n - i + 1) / i
        // 先乘后除，保证整除
        long long mul = (long long)(n - i + 1);
        long long carry = 0;
        for (auto& x : res) {
            unsigned __int128 t = (unsigned __int128)x * mul + carry;
            x = t % B;
            carry = t / B;
        }
        while (carry) {
            res.push_back(carry % B);
            carry /= B;
        }
        
        // 除以 i
        long long rem = 0;
        for (int j = (int)res.size() - 1; j >= 0; j--) {
            unsigned __int128 t = (unsigned __int128)res[j] + (unsigned __int128)rem * B;
            res[j] = t / i;
            rem = t % i;
        }
        while (res.size() > 1 && res.back() == 0) res.pop_back();
    }
    return res;
}

void print(const BigInt& a) {
    if (a.empty()) {
        printf("0\n");
        return;
    }
    printf("%lld", a.back());
    for (int i = (int)a.size() - 2; i >= 0; i--) {
        printf("%09lld", a[i]);
    }
    printf("\n");
}

int main() {
    int k, w;
    scanf("%d%d", &k, &w);
    
    int max_digit = (1 << k) - 1; // 2^k - 1
    int len = w / k;
    int p = w % k;
    
    // 至少需要 2 位，2 位需要至少 k+1 个二进制位
    if (w < k + 1) {
        printf("0\n");
        return 0;
    }
    
    BigInt ans; // 初始为 0
    
    // 情况1: 位数为 2 ~ len
    for (int m = 2; m <= len; m++) {
        ans = add(ans, C(max_digit, m));
    }
    
    // 情况2: 位数为 len+1，最高位 < 2^p
    if (p > 0) {
        int first_limit = (1 << p);
        for (int i = 1; i < first_limit; i++) {
            ans = add(ans, C(max_digit - i, len));
        }
    }
    
    print(ans);
    return 0;
}

关键细节

压位高精度：用 B = 10^9 压位，每段存 9 位十进制数。__int128 确保中间乘积不溢出。
组合数计算：用递推方式，每一步先乘 (n-i+1) 再除 i。由于 C(n, m) 一定是整数，整除不会丢失精度。
边界情况：(w < k+1) 时无法组成 2 位 (2^k) 进制数，输出 0。

执行流程

以样例 (k=3, w=7) 为例：

(max_digit = 2^3 - 1 = 7)
(len = 7 / 3 = 2)
(p = 7 % 3 = 1)

情况 1： (m = 2)

(C(7, 2) = 21)

情况 2： (p = 1 > 0)，最高位取值范围 ([1, 2^1-1] = [1, 1])

(i = 1)：(C(7-1, 2) = C(6, 2) = 15)

答案： (21 + 15 = 36)

这与样例输出一致。

调试记录

第一次实现时犯了一个错误：忘记处理 (w < k+1) 的边界情况。

当 (w < k+1) 时，即使按公式计算，(len = 0) 或 (len = 1)，循环范围 m = 2 到 len 不会执行，情况 2 也不满足条件，最终输出 0。但更清晰的写法是在开头直接判断，避免读者困惑。

复杂度分析

组合数计算：每次 (O(m \cdot \log_B(ans)))，其中 (\log_B(ans)) 是高精度数的位数。
总组合数调用次数：(O(len + 2^p))，即 (O(w/k + 2^k))。
(k \le 15)，(w \le 200000)，(2^k \le 32768)，完全在可接受范围内。

总结

这道题看似复杂，本质是组合计数的直接应用。关键洞察有两个：

「严格递增」等价于「选数即确定」——不需要考虑排列，直接计算组合数。
最高位的特殊约束需要单独枚举——由于最高位的二进制位数限制，它的取值范围小于其他位。

高精度实现是技术活，但思路本身很简洁。

Self-Review

这道题的核心在于正确建模——识别出组合数结构后，剩下的就是实现细节。高精度压位和 __int128 的使用是保证正确性和性能的关键。

不过这道题其实不适合做交互式模拟器，因为它是一个纯计数问题，没有「逐步执行」的可视化空间。如果要做可视化，可能需要展示组合数计算的过程，但那会显得有点刻意。

洛谷验证

提交记录：rid=287991152