纸老虎序列¶

解法与署名¶

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

分段回溯与有界缓存提供占用更少字符存储的并列方案，程序为 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 .先自行编译程序，再运行：

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

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

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

程序与算法	最慢中位数（秒）	峰值（MiB）	0.5 秒参考时限
共享后缀	0.070396	9.04	已测输入通过
分段回溯与有界缓存	0.069889	5.36	已测输入通过

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