# 纸老虎序列

## 解法与署名

首选出题人的“共享后缀”存储方法，程序为 [std.cpp](std.cpp)。Codex（GPT-6）按输入轮数分配长度表，精确分配最终字符区，并整理循环复制的边界。

[分段回溯与有界缓存](solution-alternative.zh.md)提供占用更少字符存储的并列方案，程序为 [alternative.cpp](alternative.cpp)。共享后缀保证构造的线性时间；回溯方案用少量缓存换取额外的区间分解，按需要选用。

## 所有版本共用一个后缀

每轮只在前面添加字符，所以 $S_i$ 是 $S_{i+1}$ 的后缀，进而是最终字符串 $S_N$ 的后缀。记 $L_i=|S_i|$ ，先按

$$L_i=L_{i-1}+\left\lceil\frac{L_{i-1}}5\right\rceil$$

计算全部长度。分配长度为 $L_N$ 的字符数组，把初始串放在区间 $[L_N-L_0,L_N)$ .此后第 $i$ 个版本始终位于 $[L_N-L_i,L_N)$ ，无需保存各版本副本。

## 增长时的复制

设增长前版本起点为 $b$、长度为 $L$ ，新增长度为 $D$ .依次写入

$$\mathrm{Text}[b-D+k]=\mathrm{Text}[b+(p_i+k)\bmod L],\qquad 0\le k<D$$

所有写入位置都在 $b$ 左侧，读取位置都在当前版本内。因此读写区间不重叠，复制过程中不会读到刚加入的内容。完成后起点变为 $b-D$ .

## 正确性

初始串在指定后缀内。若当前后缀正确，上式按题目规定的循环下标依次写出整个新增前缀，原后缀保持正确，因此增长后的后缀恰好为下一版本。归纳得到所有版本正确。查询 $q$ 时，从 $L_N-L_q$ 输出恰好 $L_q$ 个字符即可。

## 复杂度与边界

设 $Z$ 为全部输出字符数，包含换行。初始字符加历次新增字符正好是 $L_N$ ，总时间为 $O(N+L_N+Z+1)$ ，空间为 $O(N+L_N)$ .无需在每轮移动已经存在的字符。

长度表必须有 $N+1$ 项，包括版本 $0$ .本题最大初始长度为 $10$ ，执行 $70$ 次上述递推得到最大最终长度 $4055267$ ；此结论由长度递推得出，不需要把数组固定开到更大的常量。所有查询不同，最多输出 $24331433$ 个字符串字符，再加换行。

当 $N=0$ 时直接查询初始版本；当 $M=0$ 时没有输出。参数 $p_i$ 必须按增长前长度取模，抄取跨越末尾时仍按旧版本循环。

## 验证与使用

固定种子的十份正式输入配方见 `tests/plan.json` .先自行编译程序，再运行：

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

省略 `--std` 仅生成输入；`--case 01` 选择指定用例。小规模独立验证见 [check_r16.py](../../../tools/check_r16.py)，范围校验见 [validate_r16.py](../../../tools/validate_r16.py)。五轮时间、内存、输入和程序哈希见[测量记录](../../../docs/benchmark-R16.json)。环境与校准方法见[评测说明](../../../docs/评测环境与性能.md)。

## 实测结果

Intel Core Ultra 9 275HX、Windows 11、GCC 16.2.0、C++17 -O2。两份程序在相同十份正式输入上交替运行五轮。时间取每个用例中位数的最大值，包含启动与输入输出；峰值工作集独立测量，包含运行时开销。

| 程序与算法 | 最慢中位数（秒） | 峰值（MiB） | 0.5 秒参考时限 |
| --- | ---: | ---: | --- |
| [共享后缀](std.cpp) | 0.070396 | 9.04 | 已测输入通过 |
| [分段回溯与有界缓存](alternative.cpp) | 0.069889 | 5.36 | 已测输入通过 |

时限由标程最慢中位数乘以 2，向上取整到 0.5 秒得到。原始轮次、输入、源码和程序哈希见[测量记录](../../../docs/benchmark-R16.json)。其他评测机需重新校准；这些测量只描述随附实现及已测输入。