简单分析¶

解法与署名¶

出题人解法：统计有效二进制位数与其中的 \(1\) 的个数。Codex（GPT-6）明确降幂预处理的适用边界，整理实现与验证；未更换该计数算法。程序：std.cpp。

题目保证初始指数 \(e\) 满足 \(0\le e<\text{modulus}-1\) ，所以执行取模后指数仍为 \(e\) .辅助参数的具体值不会影响后续循环次数。计数对象是 multiply 的调用，而不是乘法模块内部使用多少条算术指令。

若字符串只包含零，指数为零，循环不执行，答案为零。

否则，忽略前导零，设剩余位数为 \(L\) ，其中 \(1\) 的个数为 \(w\) .循环从低位到高位处理每一位，每遇到一个 \(1\) ，调用一次更新结果的乘法，共 \(w\) 次。

指数每轮右移一位。前 \(L-1\) 次右移后仍为正数，会调用一次平方；最后一次右移后为零，不再平方。因此答案为

\[ L+w-1 \]

两类调用对应代码中的两处 multiply ，已经覆盖全部调用，且没有重复计算。

读入一个字符串后从左向右扫描。第一次遇到 \(1\) 后开始累加有效长度，同时累加 \(1\) 的数量。无需把大整数转换为机器整数，也无需执行取模或真正的模乘。

设所有字符串的总长度为 \(S\) ，最长字符串长度为 \(B\) .时间 \(O(S+Q+1)\) ，当前逐串读入实现使用 \(O(B+1)\) 空间。正指数的答案不超过 \(2L-1\) ，当前范围内最大为 \(4199999\) ，有符号 32 位整数足够。

逐位递推与“每个有效零加一、每个一加二，最后减一”只是同一计数恒等式的写法，不另列独立算法。字面执行快速幂循环用于小规模验证；对长二进制串反复进行大整数右移没有必要。

固定种子的正式输入配方见 tests/plan.json .自行编译程序后运行：

python tests/generate.py --out-dir <output-directory> --std <compiled-program>

省略 --std 仅生成输入；--case 01 选择指定用例。独立验证见 check_r15_followup.py，五轮计时、内存与哈希见测量记录，环境见评测说明。

独立验证逐次模拟条件乘法与平方调用，覆盖所有长度不超过十的非空二进制串及随机长串；压力数据覆盖总长上限、全零、全一、单个置位和大量短查询。

在 Intel Core Ultra 9 275HX、Windows 11、GCC 16.2.0、C++17 -O2 环境下，每份程序在相同的十份正式输入上运行五轮。表中时间为各用例中位耗时的最大值，包含进程启动与输入输出；内存为独立测得的峰值工作集，包含运行时开销。

程序与算法	最慢中位数（秒）	峰值（MiB）	0.5 秒参考时限
有效位与置位数统计	0.108609	9.95	已测输入通过

参考时限由标程最慢中位数乘以 2，再向上取整到 0.5 秒得到。完整轮次、输入与源码哈希见测量记录。其他评测机需要重新校准。