# ARC099F Eating Symbols Hard

Author: Fanyi Pu

Published: 2020-03-04

Canonical: <https://pufanyi.com/blog/oi-icpc/atcoder/arc099-d>

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|\le 250000$。

考虑构造一波类似生成函数的东西 $f(x)=\sum_{i=-\infty}^{+\infty}A_ix^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$，算出这个多项式的值然后哈希一下即可。

[代码](https://atcoder.jp/contests/arc099/submissions/10480687)