装备增幅题解¶
出题人解法：十进制零一编码、等宽分块前缀表与块内枚举。 Codex（GPT-6）整理 C++17 实现、末块边界，并提供按低位剪枝的表生成程序；查询算法保持不变。
1. 编码候选整数¶
二进制数字只有零和一，所以成功值的每个十进制数字也只能是零或一。设十进制位数上界为 \(D\) ，本题 \(D=30\) .把十进制零一串的各位当成二进制位，得到掩码 \(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 .数据覆盖零、最大整数、零一十进制串、块边界和随机上界。小规模校验直接枚举整数，逐位比较它的两种表示；完整前缀表另逐项核对。参考时限见评测环境与性能。