ARC099F Eating Symbols Hard 题解

ARC099F Eating Symbols Hard

题意

• 有一个长度为 $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;
}