P7044. [MCOI-03] 括号

Statement

定义一个括号串的 $0$ 级偏值为将该括号串修改为合法括号串需要的最小操作数。一次操作你可以在一个位置添加一个括号或删除一个位置的括号。

定义一个括号串的 $i$（$1 \le i \le n$）级偏值为该串所有子串的 $i - 1$ 级偏值之和。

给你一个长度为 $n$ 的括号串 $s$ 和一个正整数 $k$，求 $s$ 的 $k$ 级偏值。答案对 $998244353$ 取模。

数据范围：$1 \le n, k \le 10 ^ 6$。

---

Solution

下面的 $k$ 在题面的基础上 $-1$。

将一个括号串修改为合法括号串需要的最小操作数，等于它不匹配的括号个数。

一个子串的 $0$ 级偏值中，一个左括号有贡献，一定是没有与之匹配的右括号。右括号同理。

那么一个子串 $s[l : r]$ 的贡献就是 $\binom{l - 1 + k} k \cdot \binom{n - r + k} k \cdot f(s[l : r])$，其中 $f(t)$ 表示字符串 $t$ 中不匹配的括号个数。这是经典插板法。

因为 $n$ 到了 $10^6$，枚举每个子串 $s[l : r]$ 都不行，所以考虑从 $1$ 到 $n$ 枚举 $r$，并同时维护 $\text{now}$ 表示 $\sum_{l = 1} ^ r \binom{l - 1 + k} k \cdot f(s[l : r])$。当右端点 $r$ 移动时，分类讨论：

• 如果 $s_r$ 是左括号，那么肯定没有与之匹配的右括号，$\text{now} \leftarrow \text{now} + \sum_{l = 1} ^ r \binom{l - 1 + k} k$。
• 否则 $s_r$ 是右括号，如果有与之匹配的左括号（假定在 $t$），那么 $\text{now} \rightarrow \text{now} - \sum_{l = 1} ^ t \binom{l - 1 + k} k + \sum_{l = t + 1} ^ r \binom{l - 1 + k} k$。
• 否则 $s_r$ 是右括号，且没有与之匹配的左括号，那么 $\text{now} \leftarrow \text{now} + \sum_{l = 1} ^ r \binom{l - 1 + k} k$。

可以看到所有的 $\sum$ 都可以维护 $\binom{l - 1 + k} k$ 的前缀和快速算出。在每个 $r$ 处统计 $\binom{n - r + k} k \cdot \text{now}$ 的和即为答案。

时间复杂度 $O(n)$。

---

Code

#include <bits/stdc++.h>
typedef long long LL; const int N = 2e6 + 7, mod = 998244353;
LL qpow(LL a, int b) {
    LL s = 1;
    while(b) {
        if(b & 1) s = s * a % mod;
        b >>= 1, a = a * a % mod;
    }
    return s;
}
int n, k, stk[N], top = 0; char str[N]; LL fac[N], invf[N], s[N];
LL C(int n, int m) { return fac[n] * invf[n - m] % mod * invf[m] % mod; }
int main() {
    scanf("%d%d%s", &n, &k, str + 1), k--, fac[0] = 1;
    for(int i = 1; i <= n * 2; i++) fac[i] = fac[i - 1] * i % mod;
    invf[n * 2] = qpow(fac[n * 2], mod - 2);
    for(int i = n * 2; i; i--) invf[i - 1] = invf[i] * i % mod;
    for(int i = 1; i <= n; i++) s[i] = (s[i - 1] + C(i - 1 + k, k)) % mod;
    LL now = 0, ans = 0;
    for(int i = 1; i <= n; i++) {
        if(str[i] == '(') stk[++top] = i, now = (now + s[i]) % mod;
        else if(top) {
            int t = stk[top--];
            now = (now + s[i] - s[t] * 2 + mod * 2) % mod;
        } else now = (now + s[i]) % mod;
        ans = (ans + C(n - i + k, k) * now) % mod;
    }
    return printf("%lld\n", ans), 0;
}