#arc099d. [arc099_d]Eating Symbols Hard

[arc099_d]Eating Symbols Hard

你有一个初始为 00 的数组和一个初始在 00 的指针,范围可以看做无限。

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

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

求有多少个子串,使得执行完子串的操作后,数组和执行完整个串是一样的。

1N2500001 \leq N \leq 250000