ARC099F Eating Symbols Hard 题解
Visits: 304
题意
- 有一个长度为 $2 \times 10^9 + 1$ 的整数序列 $a_{-10^9 \dots 10^9}$,和一个整数 $p$,一开始均为 $0$。
- 对于一个仅包含
+-><
的字符串,按顺序依次执行每个字符对应的操作,可以得到新的 $a$ 序列。 - 每个字符对应的操作如下:
+
:$a_p$ 加上 $1$。-
:$a_p$ 减去 $1$。>
:$p$ 加上 $1$。<
:$p$ 减去 $1$。
- 现在有一个长度为 $n$ 的仅包含
+-><
的字符串 $s$,问有多少个 $s$ 的非空子串得到的 $a$ 序列与 $s$ 得到的 $a$ 序列一样。 - $n \le 2.5 \times 10^5$。
题解
首先对于 $a$ 显然可以 hash,hash 函数设为模意义下的 $\sum_{i=-10^9}^{10^9} a_ix^i$,其中 $x$ 是一个自己设定的 base,注意可能要多个 base/mod。
对于一个操作序列,我们可以得到其操作完后的 hash 值以及 $p$ 所在的位置 $(h,p)$,显然这个信息是可以合并的,$\operatorname{merge}((h_i,p_i), (h_j,p_j)) = (h_i + h_jx^{p_i}, p_i + p_j)$。
预处理出 $s$ 的每个前缀 $s[:i]$ 对应的 $(h_i,p_i)$,题目要求 $s$ 与 $s[i:j]$ 得到的 $h$ 相等,等价于 $s[:i-1] + s$ 与 $s[:j]$ 得到的 $h$ 相等,即 $h_{i-1} + h_{n}x^{p_{i-1}} = h_j$。
从左往右扫 $j$,用个 map
记录 $h_{i-1} + h_nx^{p_{i-1}}$ 的值的个数即可,时间复杂度 $\mathcal O(n \log n)$。
代码
const int N = 2.5e5 + 7, M = 2;
int n;
char s[N];
struct H {
vector<modint> a;
inline H() { a.resize(M); }
inline modint &operator [] (int i) { return a[i]; }
inline friend bool operator < (H x, H y) { return x.a < y.a; }
inline friend H operator + (H x, H y) {
for (int i = 0; i < M; i++) x[i] += y[i];
return x;
}
inline friend H operator - (H x, H y) {
for (int i = 0; i < M; i++) x[i] -= y[i];
return x;
}
inline friend H operator * (H x, H y) {
for (int i = 0; i < M; i++) x[i] *= y[i];
return x;
}
} a[N], x, y, h[N];
map<H, int> f;
ll ans;
int main() {
srand(time(0));
rd(n), rds(s, n);
for (int i = 0; i < M; i++)
a[0][i] = 1, x[i] = rdm(1, P - 1), y[i] = 1 / x[i];
for (int i = 1; i <= n; i++)
switch (s[i]) {
case '+' : h[i] = h[i-1] + (a[i] = a[i-1]); break;
case '-' : h[i] = h[i-1] - (a[i] = a[i-1]); break;
case '>' : h[i] = h[i-1], a[i] = a[i-1] * x; break;
case '<' : h[i] = h[i-1], a[i] = a[i-1] * y; break;
}
for (int i = 1; i <= n; i++) ++f[h[i-1]+h[n]*a[i-1]], ans += f[h[i]];
print(ans);
return 0;
}