# 装备增幅题解

**出题人解法：十进制零一编码、等宽分块前缀表与块内枚举。** Codex（GPT-6）整理 C++17 实现、末块边界，并提供按低位剪枝的表生成程序；查询算法保持不变。

## 1. 编码候选整数

二进制数字只有零和一，所以成功值的每个十进制数字也只能是零或一。设十进制位数上界为 $D$ ，本题 $D=30$ .把十进制零一串的各位当成二进制位，得到掩码 $M$ ，其对应十进制整数为

$$S(M)=\sum_{i=0}^{D-1}M_i10^i$$

于是成功条件等价于

$$S(M)\mathbin{\&}M=M$$

只需知道 $S(M)$ 的低 $D$ 个二进制位；更高位对应的十进制数字全为零。实现以无符号 32 位整数计算十的幂和求和，溢出按模 $2^{32}$ 定义，足以保留全部所需位。不能改用可能溢出的有符号整数。

十进制零一串与掩码的大小顺序一致。求出不超过 $N$ 的最大候选掩码 $B$ ：从最高位扫描，零和一照抄；一旦遇到大于一的数字，该位置及所有较低位置都填一。这样该位置已经严格小于 $N$ ，低位取一即可最大化。若没有遇到这样的数字，直接转换。

## 2. 前缀表与查询

取块宽 $L$ ，保存每个边界 $tL$ 以内成功掩码的数量 $C_t$ ，另存全域末端的总数。对于上界 $B$ ，答案先取 $C_{\lfloor B/L\rfloor}$ ，再枚举该边界之后到 $B$ 的掩码，按位计算并检查成功条件。

如果相邻表项相等，该块没有成功值，可以直接跳过。零掩码已经包含在首项 $C_0=1$ 中，不能重复统计。最后一个表项对应 $2^D-1$ ，用于不足整块的末尾。

本实现 $L=160000$ ，表有 6712 项，包含总数 715704。`std.cpp` 与 `prefix-table.hpp` 一起编译；提交到只接受一个文件的评测系统时，将头文件中的表展开到源码中。50 KB 限制针对提交程序，不包含数据生成与验证工具。

## 3. 可重复生成前缀表

出题人的直接制表方法枚举全部 $2^D$ 个掩码，逐个用 $O(D)$ 时间判定。

随附 `tests/generate-table.cpp` 使用同一个条件提前剪枝。按十进制位从低到高选择零或一。确定第 $i$ 位后，之后加入的 $10^j$（$j>i$）均是 $2^{i+1}$ 的倍数，不会改变二进制第 $i$ 位。因此若选择一而对应二进制位为零，就不再扩展这个分支；选零没有限制。

每个成功掩码恰好生成一次，每个保留前缀至少可以用全零后缀扩展为成功掩码。设成功掩码数为 $K$ ，则搜索访问 $O(DK)$ 个状态；排序后线性扫描即可生成相同前缀表，总代价为 $O(DK+K\log K+2^D/L)$ ，空间为 $O(K+D+2^D/L)$ .这项改进发生在制表阶段。

编译这个生成器并将标准输出保存为 `prefix-table.hpp` ，即可重建随附表。输出不依赖随机数或平台整数溢出行为以外的假设；所用溢出均为 C++ 定义的无符号运算。

## 正确性与复杂度

编码覆盖所有可能成功的整数且保持顺序；前缀表与剩余枚举无重叠地覆盖全部 $M\le B$ ，每个掩码按等价条件判定，所以答案正确。

使用预计算表时，$q$ 次查询耗时 $O(qDL)$ ，运行空间为 $O(2^D/L+D)$ .表的离线生成成本见上节。表扫描法避免在每次启动时生成全部成功值，适合本题对代码长度和查询数量的限制；没有声称它在每种参数下都最快。

## 数据与验证

`tests/generate.py` 支持 `--out-dir` 、`--case` 与 `--std` .数据覆盖零、最大整数、零一十进制串、块边界和随机上界。小规模校验直接枚举整数，逐位比较它的两种表示；完整前缀表另逐项核对。参考时限见[评测环境与性能](../../../docs/评测环境与性能.md)。