AT_arc077_d [ARC077F] SS

我们将由两个相同字符串拼接而成的字符串称为“偶字符串”。例如，`xyzxyz` 和 `aaaaaa` 是偶字符串，而 `ababab` 和 `xyzxy` 则不是。 对于非空字符串 $S$，定义 $f(S)$ 为“在 $S$ 后追加若干（至少 $1$ 个）字符后得到的所有偶字符串中长度最短的一个”。例如，$f($`abaaba`$)= $`abaababaab`。可以证明，对于任意非空字符串，这样的字符串仅有唯一一个。 给定一个仅包含小写英文字母的偶字符串 $S$。请你计算 $f^{10^{100}}\ (S)$ 的第 $l$ 个字母到第 $r$ 个字母之间，各个小写英文字母出现的次数。 这里 $f^{10^{100}}(S)$ 表示对 $S$ 连续应用 $f$ 操作 $10^{100}$ 次所得的字符串，即 $S$ 经过 $10^{100}$ 次 $f$ 变换后的字符串。

输入由一行组成，包含： > $S$ $l$ $r$

请输出 $26$ 个用空格分隔的整数，第 $i$ 个表示 $f^{10^{100}}(S)$ 的第 $l$ 个字母到第 $r$ 个字母之间，第 $i$ 个英文字母在这段区间中出现的次数。

## 限制条件 - $2 \leq |S| \leq 2 \times 10^5$ - $1 \leq l \leq r \leq 10^{18}$ - $S$ 仅由小写英文字母组成、且是偶字符串。 - $l,r$ 均为整数。 ## 样例解释 1 $f($`abaaba`$)= $`abaababaab`，因此 $f^{10^{100}}(S)$ 的前 $10$ 个字符也就是 `abaababaab`。所以第 $6$ 到第 $10$ 个字符是 `abaab`。在 `abaab` 中，`a` 出现了 $3$ 次，`b` 出现了 $2$ 次，`c$ 至 $z$ 都未出现，所以输出 $1$ 号为 $3$，$2$ 号为 $2$，其余 $24$ 个均为 $0$。 由 ChatGPT 5 翻译