P15122 [ICPC 2024 LAC] Harmonic Operations

在这个问题中，我们考虑三种可以应用于任何长度 $|t| \ge 2$ 的基于 0 起始的字符串 $t$ 的操作。 - $I(t)$：反转 $t$。 - $R(t, D)$：将 $t$ 向右循环移位 $D$ 个位置，其中 $D$ 是一个小于 $|t|$ 的正整数。也就是说，对于每个 $0 \le i < |t|$，$R(t, D)$ 中位置 $(i + D) \bmod |t|$ 的字符是 $t$ 中位置 $i$ 的字符。 - $L(t, D)$：与 $R(t, D)$ 类似，但将 $t$ 向左循环移位而不是向右。 例如，$I(\text{"pda"}) = \text{"adp"}$，$R(\text{"pda"}, 2) = \text{"dap"}$，以及 $L(\text{"pda"}, 2) = \text{"apd"}$。注意对于任意 $t$ 和任意 $D$，都有 $|I(t)| = |R(t, D)| = |L(t, D)| = |t|$。 当一系列上述操作应用于一个字符串时，它们按照列表顺序依次执行。也就是说，列表中的第一个操作应用于原始字符串，第二个操作应用于执行第一个操作后的结果，第三个操作应用于执行前两个操作后的结果，依此类推。 给定一个由小写字母组成的字符串 $S$，以及一个包含 $K$ 个操作的列表 $F_1, F_2, \dots, F_K$。你的任务是找出有多少对索引 $(i, j)$，满足 $1 \le i \le j \le K$，并且将操作子列表 $F_i, F_{i+1}, \dots, F_j$ 应用于 $S$ 后，最终结果等于 $S$。 例如，考虑 $S = \text{"pda"}$，$K = 2$，$F_1 = R(t, 2)$ 和 $F_2 = L(t, 2)$。将子列表 $F_1$ 应用于 $S$ 的结果是 $R(\text{"pda"}, 2) = \text{"dap"}$，它与 $S$ 不同。将子列表 $F_1, F_2$ 应用于 $S$ 的结果是 $L(R(\text{"pda"}, 2), 2) = L(\text{"dap"}, 2) = \text{"pda"} = S$。最后，将子列表 $F_2$ 应用于 $S$ 的结果是 $L(\text{"pda"}, 2) = \text{"apd"}$，它与 $S$ 不同。因此，在这个例子中，答案是 1。

第一行包含一个字符串 $S$（$2 \le |S| \le 2 \cdot 10^5$），由小写字母组成。 第二行包含一个整数 $K$（$1 \le K \le 2 \cdot 10^5$），表示正在考虑的操作列表中的操作数量。 接下来的 $K$ 行按列表中的顺序描述操作，每行一个操作。如果操作是 $I(t)$，则该行包含大写字母 "I"。如果操作是 $R(t, D)$，则该行包含大写字母 "R" 和整数 $D$（$1 \le D < |S|$）。最后，如果操作是 $L(t, D)$，则该行包含大写字母 "L" 和整数 $D$（$1 \le D < |S|$）。

输出一行一个整数，表示所求的对数。

翻译由 DeepSeek V3 完成