1649：【例 2】2^k 进制数

题目描述

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

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

在这里，正整数 $k$ 和 $w$ 是事先给定的。

问：满足上述条件的不同的 $r$ 共多少个？

输入格式

输入只一行，为两个正整数 $k$ 和 $w$。

输出格式

输出为一行，是一个正整数，为所求的计算结果，即满足条件的不同的 $r$ 的个数（用十进制数表示，要求最高位不得为 $0$，各数字之间不得插入数字以外的其他字符。

提示：作为结果的正整数可能很大，但不会超过 $200$ 位。

样例

样例输入 #1

3 7

样例输出 #1

36

样例解释 #1

• $k=3$，$2^k = 8$，所以 $r$ 是 $8$ 进制数。
• $w=7$ 表示 $r$ 转换为二进制后位数不超过 $7$。
• 条件 $2$：$r$ 的每一位严格递增（除最后一位外，实际上最后一位与前面也满足严格递增？条件说“除最后一位外”，意思是最后一位没有右边相邻位，所以不要求最后一位比前一位大？但整个数是从左到右严格递增的，所以最后一位比前一位大也是成立的。实际上条件：每一位严格小于它右边相邻的那一位，所以对于最后一位，没有右边相邻位，所以没有约束。因此整个序列是严格递增的。
• 求满足条件的 $r$ 的数量。
• 输出 $36$。

数据范围

对于所有数据，$1 \le k \le 9$，$k < w \le 3 \times 10^4$。

时空限制

• 时间限制：1000 ms
• 内存限制：524288 KB

注意：本题是组合计数问题。$r$ 是一个 $2^k$ 进制数，每一位数字在 $0$ 到 $2^k-1$ 之间，且从左到右严格递增（即数字单调递增）。同时，$r$ 转换为二进制后长度不超过 $w$。

设 $2^k$ 进制数的最大位数为 $L$。由于二进制位数不超过 $w$，而 $2^k$ 进制每一位对应 $k$ 位二进制（除了最高位可能不足 $k$ 位），所以有：$r$ 的位数 $len$ 满足：$(len-1) \times k < w \le len \times k$？实际上，$r$ 的二进制位数等于 $r$ 的位数乘以 $k$，但最高位可能不足 $k$ 位（因为 $r$ 的位数固定时，最高位的取值范围可能使得二进制位数减少）。更精确地，设 $r$ 有 $m$ 位，则 $r$ 的二进制位数最多为 $m \times k$，最少为 $(m-1) \times k + 1$（因为最高位至少为 $1$，所以二进制表示至少 $1$ 位）。条件要求二进制位数不超过 $w$，所以 $m$ 必须满足 $(m-1) \times k + 1 \le w$，即 $m \le \lfloor (w-1)/k \rfloor + 1$。另外，$r$ 至少 $2$ 位，所以 $m \ge 2$。

此外，由于 $r$ 是 $2^k$ 进制数，每一位数字在 $0$ 到 $2^k-1$ 之间，且严格递增（即各位数字互不相同且递增）。这相当于从 $0,1,2,\dots,2^k-1$ 这 $2^k$ 个数字中选出 $m$ 个组成一个递增序列（即组合数），但最高位不能为 $0$（因为 $r$ 是 $2^k$ 进制数，最高位不能为 $0$，否则就不是 $m$ 位数了）。所以实际上，$r$ 对应一个从 $1$ 到 $2^k-1$ 中选出 $m$ 个不同数字并按升序排列，但数字顺序就是数位顺序，所以每个组合对应一个 $r$。因此，对于固定的 $m$，方案数为 $C(2^k-1, m)$（因为最高位不能为 $0$，所以不能选 $0$，从 $1$ 到 $2^k-1$ 共 $2^k-1$ 个数中选 $m$ 个）。

但还需要考虑二进制位数不超过 $w$ 的限制。当 $m$ 固定时，$r$ 的二进制位数等于 $m \times k$ 减去前导零的个数？实际上，$r$ 的二进制表示就是将其每一位数字表示为 $k$ 位二进制（最高位可能不足 $k$ 位，因为最高位的数字可能小于 $2^{k-1}$，但二进制位数仍是 $k$ 位？例如 $k=3$，数字 $1$ 的二进制是 $001$，但作为二进制数 $q$，前导零可以去掉，所以 $q$ 的位数可能小于 $m \times k$。但题目中“转换为 $2$ 进制数 $q$ 后，$q$ 的总位数不超过 $w$”是指去掉前导零后的位数。所以我们需要确保 $r$ 的二进制表示去掉前导零后长度不超过 $w$。

由于 $r$ 的最高位不为 $0$，设为 $x$，则 $x \ge 1$，其二进制表示的长度为 $\lfloor \log_2 x \rfloor + 1$，这个长度可能小于 $k$。其余 $m-1$ 位每个都恰好占用 $k$ 位二进制（因为即使数字小于 $2^{k-1}$，在 $2^k$ 进制表示中我们仍然用 $k$ 位表示，但转换为二进制时会去掉前导零？实际上，$r$ 转换为二进制数 $q$ 的过程是：将 $r$ 的每一位数字写成二进制，然后拼接起来，去掉最高位的前导零，但中间位的前导零不能去掉（因为它们是 $k$ 位的一部分）。所以 $q$ 的总位数 = $(m-1) \times k + (\text{最高位二进制位数})$。

设最高位数字为 $x$，其二进制位数 $len_x = \lfloor \log_2 x \rfloor + 1$，则 $q$ 的总位数为 $(m-1) \times k + len_x$。条件要求 $(m-1) \times k + len_x \le w$。

由于 $x$ 的取值范围是 $1$ 到 $2^k-1$，$len_x$ 可能为 $1$ 到 $k$。因此，对于固定的 $m$，我们需要计算满足 $(m-1) \times k + len_x \le w$ 且 $1 \le x \le 2^k-1$ 的 $x$ 的个数，然后乘以从剩余数字中选出 $m-1$ 个且大于 $x$ 的组合数。

但这样计算较复杂。另一种思路：先不考虑二进制位数限制，计算所有满足严格递增且最高位非 $0$ 的 $2^k$ 进制数的个数，然后减去那些二进制位数超过 $w$ 的数。

由于 $k \le 9$，$2^k \le 512$，$2^k-1$ 不大，但 $w$ 可能很大（$3\times 10^4$），所以 $m$ 的最大值可能很大（$m \le \lfloor (w-1)/k \rfloor + 1$，最大约 $30000/1=30000$）。但 $2^k-1$ 最多 $511$，所以当 $m > 2^k-1$ 时，无法选出 $m$ 个不同数字，方案数为 $0$。因此，实际上 $m$ 不超过 $2^k-1$。

所以我们可以枚举 $m$ 从 $2$ 到 $\min(2^k-1, \lfloor (w-1)/k \rfloor + 1)$，对于每个 $m$，计算方案数。

但还需要考虑二进制位数限制：对于每个 $m$，最高位数字 $x$ 必须满足 $(m-1) \times k + len_x \le w$。由于 $len_x$ 取决于 $x$ 的大小，我们可以按 $len_x$ 分类。

令 $t = w - (m-1) \times k$，则要求 $len_x \le t$。$len_x$ 是 $x$ 的二进制位数，$x$ 在 $1$ 到 $2^k-1$ 之间。设 $cnt[l]$ 表示二进制位数为 $l$ 的数字个数（$1 \le l \le k$），则 $cnt[l] = 2^{l-1}$（因为首位为 $1$，后面 $l-1$ 位任意），但当 $l=k$ 时，最大数字为 $2^k-1$，所以 $cnt[k] = 2^{k-1}$？实际上，二进制位数为 $l$ 的数字范围是 $2^{l-1}$ 到 $2^l-1$，共 $2^{l-1}$ 个。对于 $l=k$，范围是 $2^{k-1}$ 到 $2^k-1$，共 $2^{k-1}$ 个。但注意 $x$ 不能超过 $2^k-1$，所以 $l=k$ 时确实是 $2^{k-1}$ 个。

因此，满足 $len_x \le t$ 的 $x$ 的个数为 $\sum_{l=1}^{\min(t, k)} cnt[l]$，但 $t$ 可能大于 $k$，此时所有 $x$ 都满足（因为 $len_x \le k$），所以个数为 $2^k - 1$（所有非零数字）。

对于每个这样的 $x$，我们需要从大于 $x$ 的数字中选出 $m-1$ 个（因为后面数字必须严格大于 $x$），且总数字范围是 $1$ 到 $2^k-1$，大于 $x$ 的数字有 $2^k-1 - x$ 个，所以方案数为 $C(2^k-1 - x, m-1)$。

因此，对于固定的 $m$，总方案数为：

$$\sum_{x=1}^{2^k-1} [len_x \le t] \cdot C(2^k-1 - x, m-1)$$

其中 $t = w - (m-1)k$。

由于 $2^k-1$ 最多 $511$，可以直接枚举 $x$ 计算组合数。但组合数可能很大，需要高精度计算（因为答案可能很大，不超过 $200$ 位，所以需要高精度加法和高精度组合数）。

另外，$m$ 可能达到 $511$，组合数 $C(n,m)$ 可以用递推公式 $C(n,m) = C(n-1,m-1) + C(n-1,m)$ 计算，但需要高精度。

由于 $k \le 9$，$2^k-1 \le 511$，所以我们可以预处理所有组合数 $C(i,j)$（$0 \le j \le i \le 511$），用高精度存储。然后枚举 $m$ 和 $x$ 累加。

注意：$t$ 可能小于 $1$，此时没有满足条件的 $x$，方案数为 $0$。

算法步骤：

1. 读入 $k, w$。
2. 计算 $maxm = \min(2^k-1, \lfloor (w-1)/k \rfloor + 1)$，且 $m \ge 2$。
3. 预处理高精度组合数表 $C[i][j]$（$0 \le j \le i \le 511$）。
4. 初始化答案 $ans = 0$（高精度）。
5. 枚举 $m$ 从 $2$ 到 $maxm$：
   • 计算 $t = w - (m-1) \times k$。
   • 如果 $t < 1$，跳过。
   • 枚举 $x$ 从 $1$ 到 $2^k-1$：
     • 计算 $len_x = \lfloor \log_2 x \rfloor + 1$。
     • 如果 $len_x > t$，继续。
     • 计算 $n = 2^k - 1 - x$。
     • 如果 $n < m-1$，跳过。
     • $ans += C[n][m-1]$（高精度加法）。
6. 输出 $ans$（高精度数，无前导零）。

注意：当 $t \ge k$ 时，所有 $x$ 都满足 $len_x \le t$，此时可以简化计算：方案数为 $\sum_{x=1}^{2^k-1} C(2^k-1 - x, m-1)$。令 $y = 2^k-1 - x$，则 $y$ 从 $0$ 到 $2^k-2$，求和为 $\sum_{y=0}^{2^k-2} C(y, m-1)$。根据组合恒等式 $\sum_{y=m-1}^{2^k-2} C(y, m-1) = C(2^k-1, m)$（因为 $C(m-1,m-1) + C(m,m-1) + ... + C(n,m-1) = C(n+1, m)$）。注意 $y$ 从 $0$ 开始，但 $C(y, m-1)$ 当 $y < m-1$ 时为 $0$，所以实际上求和为 $C(2^k-1, m)$。因此，当 $t \ge k$ 时，方案数就是 $C(2^k-1, m)$。这对应于二进制位数限制不起作用的情况（因为最高位二进制位数最多 $k$，而 $t \ge k$ 意味着 $(m-1)k + k \le w$，即 $mk \le w$，所以整个数的二进制位数不超过 $w$）。

因此，我们可以分两种情况：

• 如果 $m \times k \le w$，则方案数为 $C(2^k-1, m)$。
• 否则，方案数为 $\sum_{x=1}^{2^k-1} [len_x \le w - (m-1)k] \cdot C(2^k-1 - x, m-1)$。

由于 $k$ 很小，可以直接枚举 $x$。

高精度实现：可以用数组存储十进制位，实现加法和组合数递推。

注意：答案可能很大，但不超过 $200$ 位，所以高精度数组大小可以设为 $300$。