小红的可爱括号串

[题目链接](https://www.nowcoder.com/practice/ec6b4a16994b4c6cb5c156f5cb40e5ca)

思路

题目定义"可爱括号串"为前半全是左括号、后半全是右括号的偶数长度括号串，即形如 $\underbrace{((...(}_{k}\underbrace{)...))}_{k}$ 的串。我们需要统计原串中有多少个子序列构成可爱括号串。

拆解问题

一个可爱子序列由 $k$ 个 ( 紧跟 $k$ 个 ) 组成，且在原串中所有被选中的 ( 都出现在所有被选中的 ) 之前。那么，我们能否找到一个"分界点"来把选取的左右括号分开呢？

枚举第一个右括号

关键思路是：枚举可爱子序列中最左边的那个 )。假设这个 ) 在原串中的位置是 $i$ ，那么：

所有选中的 ( 都必须在位置 $i$ 之前，设位置 $i$ 之前共有 $L$ 个 (；
所有选中的 ) 都在位置 $i$ 及之后，设位置 $i$ 及之后共有 $R$ 个 )。

对于长度为 $2k$ 的可爱子序列，我们需要从 $L$ 个 ( 中选 $k$ 个，从 $R$ 个 ) 中选 $k$ 个且必须包含位置 $i$ （因为 $i$ 是最左边的 )）。包含位置 $i$ 意味着还需要从剩余 $R - 1$ 个 ) 中选 $k - 1$ 个，方案数为 $\binom{L}{k} \cdot \binom{R-1}{k-1}$ 。

用 Vandermonde 卷积化简

对 $k$ 从 $1$ 到 $\min(L, R)$ 求和：

$ $\sum_{k=1}^{\min(L,R)} \binom{L}{k} \binom{R-1}{k-1}$ $

令 $j = k - 1$ ，得到：

$ $\sum_{j=0}^{\min(L,R)-1} \binom{L}{j+1} \binom{R-1}{j}$ $

注意到 $\binom{L}{j+1} = \binom{L}{L-1-j}$ ，由 Vandermonde 卷积恒等式 $\sum_{j} \binom{a}{s-j}\binom{b}{j} = \binom{a+b}{s}$ ，取 $a = L$ , $b = R-1$ , $s = L-1$ ，得到：

$ $\sum_{j=0} \binom{L}{L-1-j} \binom{R-1}{j} = \binom{L+R-1}{L-1}$ $

最终算法

预处理阶乘及其逆元，以便 $O(1)$ 计算组合数。
计算前缀 ( 计数和后缀 ) 计数。
枚举每个 ) 的位置 $i$ ，令 $L$ = 位置 $i$ 之前的 ( 个数， $R$ = 位置 $i$ 及之后的 ) 个数，累加 $\binom{L+R-1}{L-1}$ 。

以示例 1 为例， $s =$ (())：

位置 2 处的 )： $L = 2, R = 2$ ，贡献 $\binom{3}{1} = 3$ ；
位置 3 处的 )： $L = 2, R = 1$ ，贡献 $\binom{2}{1} = 2$ ；
总计 $3 + 2 = 5$ 。

代码

C++
Java

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

long long fac[200005], inv_fac[200005];

long long power(long long a, long long b, long long mod) {
    long long res = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

void precompute(int n) {
    fac[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = fac[i-1] * i % MOD;
    inv_fac[n] = power(fac[n], MOD - 2, MOD);
    for (int i = n - 1; i >= 0; i--) inv_fac[i] = inv_fac[i+1] * (i+1) % MOD;
}

long long C(int n, int r) {
    if (r < 0 || r > n) return 0;
    return fac[n] % MOD * inv_fac[r] % MOD * inv_fac[n-r] % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    string s;
    cin >> s;

    precompute(2 * n);

    vector<int> pre(n + 1, 0);
    for (int i = 0; i < n; i++) {
        pre[i+1] = pre[i] + (s[i] == '(');
    }

    vector<int> suf(n + 1, 0);
    for (int i = n - 1; i >= 0; i--) {
        suf[i] = suf[i+1] + (s[i] == ')');
    }

    long long ans = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == ')') {
            int L = pre[i];
            int R = suf[i];
            if (L >= 1 && R >= 1) {
                ans = (ans + C(L + R - 1, L - 1)) % MOD;
            }
        }
    }

    cout << ans << endl;
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    static final int MOD = 1_000_000_007;
    static long[] fac, invFac;

    static long power(long a, long b, long mod) {
        long res = 1;
        a %= mod;
        while (b > 0) {
            if ((b & 1) == 1) res = res * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return res;
    }

    static void precompute(int n) {
        fac = new long[n + 1];
        invFac = new long[n + 1];
        fac[0] = 1;
        for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % MOD;
        invFac[n] = power(fac[n], MOD - 2, MOD);
        for (int i = n - 1; i >= 0; i--) invFac[i] = invFac[i + 1] * (i + 1) % MOD;
    }

    static long C(int n, int r) {
        if (r < 0 || r > n) return 0;
        return fac[n] % MOD * invFac[r] % MOD * invFac[n - r] % MOD;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String s = br.readLine().trim();

        precompute(2 * n);

        int[] pre = new int[n + 1];
        for (int i = 0; i < n; i++) {
            pre[i + 1] = pre[i] + (s.charAt(i) == '(' ? 1 : 0);
        }

        int[] suf = new int[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            suf[i] = suf[i + 1] + (s.charAt(i) == ')' ? 1 : 0);
        }

        long ans = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == ')') {
                int L = pre[i];
                int R = suf[i];
                if (L >= 1 && R >= 1) {
                    ans = (ans + C(L + R - 1, L - 1)) % MOD;
                }
            }
        }

        System.out.println(ans);
    }
}

复杂度分析

时间复杂度： $O(n)$ 。预处理阶乘和逆元 $O(n)$ ，遍历字符串 $O(n)$ ，每个位置的组合数计算 $O(1)$ 。
空间复杂度： $O(n)$ 。存储阶乘数组、前缀和数组和后缀和数组。