ARC099F Eating Symbols Hard 题解

作者: xht37 分类: 题解 发布时间: 2020-04-28 20:36

点击数:110

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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注