题目链接

小红的可爱括号串

题目描述

一个括号串被称为“可爱的”，当且仅当它满足以下所有条件：

  1. 长度为偶数。
  2. 左半部分全部是 (。
  3. 右半部分全部是 )。
  4. 左右括号数量相等。

例如 (()) 是可爱的，因为它由 ( 和 ) 组成，长度为4，前2个是 (，后2个是 )。

给定一个长度为 的括号串，求出其中有多少个子序列是“可爱的”。答案需要对 取模。

解题思路

这个问题要求我们统计特定模式 ((...)) 的子序列数量。一个直接的想法是枚举所有可能的子序列，但那会非常慢。一个更好的方法是使用组合计数。

核心思路

一个可爱的括号串由 个 ( 和 个 ) 组成，并且所有的 ( 都在 ) 的前面。我们的任务就是在给定的字符串中，找出所有满足这样条件的子序列。

我们可以枚举每一个 (，并计算它对总答案的贡献。具体来说，我们可以枚举字符串中的每一个 (，并假设它是某个可爱括号串中 最右边的一个 (。

假设我们在位置 找到了一个 ( (s[i] == '(')。

  • 在它前面（不包括位置 ），假设有 个 (。
  • 在它后面（不包括位置 ），假设有 个 )。

现在，我们要组成一个长度为 的可爱串，其中我们已经钦定了位置 的 ( 是第 个（也就是最右边那个）左括号。

  • 为了凑齐左边的 个 (，我们需要从前面的 个 ( 中再选出剩下的 个。选择的方案数是组合数 。
  • 为了凑齐右边的 个 )，我们需要从后面的 个 ) 中选出全部 个。选择的方案数是组合数 。

因此，对于位置 的这个 (，它作为最右边的左括号，能形成的可爱串总数为：

这个求和式看起来很复杂。幸运的是，我们可以使用一个组合恒等式——范德蒙德卷积的一个推论来简化它。该恒等式为：

我们对我们的求和式进行变形：。

注意到两个组合数的下标之和为 ，这是一个与 无关的常数。根据范德蒙德卷积，这个和就等于 。

这样，问题就大大简化了。

高效计算组合数

由于 的范围达到了 ，我们无法使用 的动态规划来预处理组合数。我们需要一种更高效的方法。

我们可以利用公式 来计算。因为需要对一个大素数 取模，所以除法要转换为乘以模逆元。

我们可以用 的时间预处理出到 为止的所有数的阶乘 fact[i] 和阶乘的模逆元 invFact[i]。之后，每次计算组合数都只需要 的时间。

最终算法

  1. 花费 时间预处理阶乘和阶乘的模逆元。
  2. 花费 时间预处理后缀 ) 数量数组 suffix_right。suffix_right[i] 表示从位置 到字符串末尾 ) 的数量。
  3. 初始化 ans = 0，以及一个计数器 left_count = 0 用于记录遍历过程中遇到的 ( 的数量。
  4. 从左到右遍历字符串（ from to ):
    • 如果 s[i] == '(':
      • 获取其前面的 ( 数量 。
      • 获取其后面的 ) 数量 。
      • 如果 ，则计算其贡献 并累加到 ans 中。
      • 更新 left_count，将其加一。
  5. 返回最终的 ans。

这个算法的总时间和空间复杂度都是 。

代码

#include <iostream>
#include <vector>
#include <string>

using namespace std;

const int MOD = 1e9 + 7;

vector<long long> fact;
vector<long long> invFact;

long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

long long modInverse(long long n) {
    return power(n, MOD - 2);
}

void precompute_factorials(int n) {
    fact.resize(n + 1);
    invFact.resize(n + 1);
    fact[0] = 1;
    invFact[0] = 1;
    for (int i = 1; i <= n; i++) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }
    invFact[n] = modInverse(fact[n]);
    for (int i = n - 1; i >= 1; i--) {
        invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;
    }
}

long long nCr_mod_p(int n, int r) {
    if (r < 0 || r > n) {
        return 0;
    }
    return (((fact[n] * invFact[r]) % MOD) * invFact[n - r]) % MOD;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    precompute_factorials(n);

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

    long long ans = 0;
    int left_count = 0;

    for (int i = 0; i < n; ++i) {
        if (s[i] == '(') {
            int L = left_count;
            int R = (i + 1 < n) ? suffix_right[i + 1] : 0;
            if (R > 0) {
                ans = (ans + nCr_mod_p(L + R, R - 1)) % MOD;
            }
            left_count++;
        }
    }

    cout << ans << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    static final int MOD = 1_000_000_007;
    static long[] fact;
    static long[] invFact;

    static long power(long base, long exp) {
        long res = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % MOD;
            base = (base * base) % MOD;
            exp /= 2;
        }
        return res;
    }

    static long modInverse(long n) {
        return power(n, MOD - 2);
    }

    static void precomputeFactorials(int n) {
        fact = new long[n + 1];
        invFact = new long[n + 1];
        fact[0] = 1;
        invFact[0] = 1;
        for (int i = 1; i <= n; i++) {
            fact[i] = (fact[i - 1] * i) % MOD;
        }
        invFact[n] = modInverse(fact[n]);
        for (int i = n - 1; i >= 1; i--) {
            invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;
        }
    }

    static long nCr_mod_p(int n, int r) {
        if (r < 0 || r > n) {
            return 0;
        }
        long numerator = fact[n];
        long denominator = (invFact[r] * invFact[n - r]) % MOD;
        return (numerator * denominator) % MOD;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();

        precomputeFactorials(n);

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

        long ans = 0;
        int leftCount = 0;

        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '(') {
                int L = leftCount;
                int R = (i + 1 < n) ? suffixRight[i + 1] : 0;
                if (R > 0) {
                    ans = (ans + nCr_mod_p(L + R, R - 1)) % MOD;
                }
                leftCount++;
            }
        }

        System.out.println(ans);
    }
}

import sys

MOD = 10**9 + 7

def precompute_factorials(n):
    fact = [1] * (n + 1)
    invFact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = (fact[i-1] * i) % MOD
    
    invFact[n] = pow(fact[n], MOD - 2, MOD)
    for i in range(n - 1, -1, -1):
        invFact[i] = (invFact[i+1] * (i+1)) % MOD
    return fact, invFact

def nCr_mod_p(n, r, fact, invFact):
    if r < 0 or r > n:
        return 0
    numerator = fact[n]
    denominator = (invFact[r] * invFact[n - r]) % MOD
    return (numerator * denominator) % MOD

def solve():
    n = int(sys.stdin.readline())
    s = sys.stdin.readline().strip()

    fact, invFact = precompute_factorials(n)

    suffix_right = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        suffix_right[i] = suffix_right[i + 1] + (1 if s[i] == ')' else 0)
    
    ans = 0
    left_count = 0
    for i in range(n):
        if s[i] == '(':
            L = left_count
            R = suffix_right[i + 1] if i + 1 < n else 0
            if R > 0:
                ans = (ans + nCr_mod_p(L + R, R - 1, fact, invFact)) % MOD
            left_count += 1
            
    print(ans)

solve()

算法及复杂度

  • 算法：组合数学、范德蒙德卷积
  • 时间复杂度：
    • 预处理阶乘和逆元阶乘的时间复杂度为 。
    • 预处理后缀 ) 数量的时间复杂度为 。
    • 主循环遍历字符串一次，复杂度为 。
    • 因此，总时间复杂度为 。
  • 空间复杂度：
    • 存储阶乘和逆元阶乘的数组需要 的空间。
    • 后缀和数组需要 的空间。
    • 因此，总空间复杂度为 。