ARC099F Eating Symbols Hard

有一段标号从 $- \infty$ 到 $+ \infty$ 的序列 $A$ ，初始是 $A_{i} = 0$ 。现在有一个人在 $0$ 位置，有一段操作序列 $s$ ，依次进行操作。

假设 $i$ 时刻这个人在位置 $p$ ，如果 $s_{i}$ 是 '+'，则将 $A_{p}$ 加 $1$ ，如果是 '-'，则减 $1$ ；如果是 '<' 则该人左移一格，否则是 '>' 则右移一格。

要求数出 $s$ 的所有连续子串中最终得到的 $A$ 与 $s$ 最终得到相同 $A$ 序列的个数。

数据范围 $| s | \leq 250000$ 。

考虑构造一波类似生成函数的东西 $f (x) = \sum_{i = - \infty}^{+ \infty} A_{i} x^{i}$ ，另外还有一个指针 $g$ ，开始是 $g$ 指向 $0$ 位置，显然初始时 $f (x) = 0$ 。

我们令 $f_{i} (x)$ 表示 $1 \sim i$ 这一段子串操作所得到的 $f$ 值， $g_{i}$ 表示 $1 \sim i$ 操作后的指针位置。考虑在末尾加入一个字符 $c$ ，如果 $c$ 是 '+' 或 '-'，那显然 ${\begin{cases} f_{i} (x) = f_{i - 1} (x) \pm x^{g_{i}} \\ g_{i} = g_{i - 1} \end{cases}$ ，同理如果 $c$ 是 '<' 或 '>'，那显然 ${\begin{cases} f_{i} (x) = f_{i - 1} (x) \\ g_{i} = g_{i - 1} \mp 1 \end{cases}$ 。

如果要计算 $[l, r]$ 的 $f$ 值，不难发现就是 $\frac{f_{r} (x) - f_{l - 1} (x)}{x^{g_{l - 1}}}$ 。

于是我们要算的就是 $f_{n} (x) = \frac{f_{r} (x) - f_{l - 1} (x)}{x^{g_{l - 1}}}$ ，考虑随便选一个 $x$ ，算出这个多项式的值然后哈希一下即可。

代码

Cite this post