ARC099D Eating Symbols Hard

题意 ： 你有一个初始为 的数组 （范围无限）和一个初始在 的指针。

给出一个长度为 的操作串 ，由 <，>，+，- 组成，其中每个字符意义如下。

• < 将指针左移一位。
• > 将指针右移一位。
• + 将指针对应位置 。
• - 将指针对应位置 。

求有多少个子串，使得执行完子串的操作后，数组和执行完整个串是一样的。（不要求指针位置相同）

，时限 。

---

Hash 题。

考虑使用经典的字符串 Hash 描述该数组。

对于数组 ，其 Hash 值定义为：

其中 是我们任选的常数。

---

记指针位置为 。

考察各个操作对 Hash 值的影响。

• 在串后添加一个 < :
• 在串后添加一个 > :
• 在串后添加一个 + :
• 在串后添加一个 - :

于是，容易求出每个前缀的 Hash 值。记执行 得到的数组的 Hash 值为 。

记执行 得到的指针位置为 。

考虑如何求出某个区间 的 Hash 值 。

位要以 为基准，故将 相减后，还需将整个数组移动 。故

我们的目标是，求出有多少组 满足 ：

枚举左端点，使用 std::map 统计符合要求的右端点个数即可。

复杂度 。