有一段标号从 \(-\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\)，算出这个多项式的值然后哈希一下即可。