题解

题目大意

给定初始字符串 $S$（长度 $n$）和参数 $k$，按以下规则不断在末尾添加字符：

1. 设当前字符串为 $T$，长度为 $L$，取其后 $k$ 个字符作为子串 $R$。
2. 找出 $R$ 在 $T$ 中所有出现的位置（包括中间出现的位置，不包含最后一个位置）。
3. 统计这些出现位置后面一个字符的频率。
4. 取频率最高的字符作为要添加的字符 $c$（频率相同取字典序最小），若 $R$ 没有在其他位置出现过，则 $c=\texttt{a}$。
5. 将 $c$ 添加到 $T$ 末尾。

现给定 $a, b$（$n < a < b \le 10^{18}$，$b-a+1 \le 10^6$），要求输出长度分别为 $a, a+1, \dots, b$ 的完整字符串（每行一个）。

思路分析

直接模拟到 $b$ 是不可能的，因为 $b$ 可达 $10^{18}$。
关键在于观察到：整个过程是一个确定性的状态转移，状态是当前的后 $k$ 个字符（长度为 $k$ 的字符串）。

核心观察

• 状态集的大小有限：最多 $26^k$ 种（虽然 $k$ 最大 $10^6$，但实际转移过程中不同状态不会无限多，因为转移规则固定，最终会进入循环）。
• 因此，从初始状态出发，经过若干步后一定会进入一个循环节。
• 我们的任务是：只生成从位置 $a$ 到 $b$ 的字符，而不必生成全部 $b$ 个字符。
• 需要高效地查询“某个状态 $R$ 在历史中出现的所有位置的后一个字符频率”。

高效维护“历史出现信息”

设 $R$ 是一个长度为 $k$ 的字符串。
我们需要知道 $R$ 在 $T$ 的所有出现位置（不包含最后一次作为后缀的位置）的后一个字符的频次统计。

我们可以动态维护：
用一个哈希表 cnt[hash(R)][ch] 记录：每当 $R$ 出现一次（不是最后一次）时，其后一个字符 $ch$ 的累计出现次数。

如何更新：

1. 初始时，扫描 $S$，对所有长度为 $k$ 的子串 $R$，如果它后面有字符 $ch$，则 cnt[hash(R)][ch]++。
2. 生成过程中，假设当前状态是 $R$，我们根据 cnt[hash(R)] 决定下一个字符 $c$。
3. 添加 $c$ 后，新的末尾 $k$ 子串是 $R'$。
   同时，我们刚刚让 $R$ 多出现了一次（即作为倒数第二个长度为 $k$ 的子串，后面跟了 $c$），所以 cnt[hash(R)][c]++。
4. 更新当前状态为 $R'$。

这样，查询下一个字符只需 $O(|\Sigma|) = O(26)$。

状态表示与滚动哈希

由于 $k$ 可能很大，不能直接存字符串，用滚动哈希（双模数哈希防止冲突）表示当前后 $k$ 个字符的哈希值。
转移时：

• 已知 $R = T[L-k+1..L]$ 的哈希值 $(h1, h2)$。
• 去掉第一个字符 $first = T[L-k+1]$，加上新字符 $c$。
• 新哈希值： $ h1' = \big((h1 - first \cdot p1^{k-1}) \cdot BASE1 + c\big) \bmod MOD1 $ 其中 $p1^{k-1}$ 是预先算好的幂。

处理超大 $b$：周期检测

我们只需要生成 $a$ 到 $b$ 的字符，但 $a$ 可能非常大（$10^{18}$ 级别），必须避免模拟到 $a$。

注意到状态转移形成一个有向图（每个状态指向下一个状态），由于状态数有限，路径必然进入循环。
我们可以模拟直到发现某个状态第二次出现，记录：

• start_pos[state]：该状态第一次出现时的字符串长度。
• char_at[pos]：字符串在位置 $pos$（$pos > n$）的字符。

发现循环后，设循环节长度为 $cycle$，那么对于任意位置 $p$，我们可以 $O(1)$ 知道它的字符： $ \text{字符} = \text{char\_at}[ \text{start} + ((p - \text{start}) \bmod cycle) ] $ 其中 $\text{start}$ 是循环开始位置。

输出部分

因为 $b-a+1 \le 10^6$，我们可以：

1. 模拟直到长度 $\min(b, \text{循环检测完成})$，并记录每个位置的字符（或只记录 $a$ 到 $b$ 的部分）。
2. 如果 $a$ 在循环内，用周期公式直接得到 $a$ 到 $b$ 的字符。
3. 最后输出时，每个长度的字符串 = 初始 $S$ + 生成的部分。

时间复杂度

• 初始统计 $S$ 中所有长度 $k$ 子串的频率：$O(n)$。
• 模拟至多 $O(\text{状态数} + (b-a+1))$ 步，状态数有限，通常远小于 $b$。
• 哈希表操作 $O(1)$，每次查询下一个字符 $O(26)$。
• 总复杂度大致 $O(n + (b-a+1) \cdot 26)$，可接受。

关键点总结

1. 状态压缩：用滚动哈希表示长度 $k$ 的字符串。
2. 频率动态更新：cnt 表记录每个状态的历史后继字符频率，避免每次扫描历史。
3. 周期检测：快速跳过巨大的 $a$ 到 $b$ 之间的大部分步数。
4. 按需输出：只生成 $a$ 到 $b$ 的字符，节省时间和空间。