# 简单分析

## 解法与署名

出题人解法：统计有效二进制位数与其中的 $1$ 的个数。Codex（GPT-6）明确降幂预处理的适用边界，整理实现与验证；未更换该计数算法。程序：[std.cpp](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` .自行编译程序后运行：

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

省略 `--std` 仅生成输入；`--case 01` 选择指定用例。独立验证见 [check_r15_followup.py](../../../tools/check_r15_followup.py)，五轮计时、内存与哈希见[测量记录](../../../docs/benchmark-R15-followup.json)，环境见[评测说明](../../../docs/评测环境与性能.md)。

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

## 实测结果

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

| 程序与算法 | 最慢中位数（秒） | 峰值（MiB） | 0.5 秒参考时限 |
| --- | ---: | ---: | --- |
| [有效位与置位数统计](std.cpp) | 0.108609 | 9.95 | 已测输入通过 |

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