HDU 5184 Brackets 卡特蘭數擴展 (組合數學 + 模逆元)

問題

給定長度 n (≤10⁶) 的合法括號序列前綴 str，求補全為完整合法括號序列的方案數模 1e9+7。多測試用例 (~2000)。

數學模型

合法括號序列 ↔ 從 (0,0) 走到 (n/2, n/2) 不超過 y=x 的路徑。
已知前綴對應走到 (a,b) (a='('數, b=')'數)。剩餘步數：左括號 L=n/2-a，右括號 R=n/2-b。
若任意前綴右括號多於左括號 → 0 方案。
否則方案數 = C(L+R, L) - C(L+R, L-1) (卡特蘭三角數 / 球ot 定理)。

公式推導

設 a = 剩餘左括號數，b = 剩餘右括號數 (a ≤ b)。
答案 = C(a+b, a) - C(a+b, a-1) = C(a+b, b) - C(a+b, b-1)。
模質數 p=1e9+7 下，預處理階乘與逆元，O(1) 計算組合數。

代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
const long long MOD = 1000000007LL;
long long fac[MAXN], ifac[MAXN], inv[MAXN];

void init() {
    inv[1] = fac[0] = ifac[0] = 1;
    for (int i = 2; i < MAXN; ++i) inv[i] = (MOD - MOD/i) * inv[MOD%i] % MOD;
    for (int i = 1; i < MAXN; ++i) {
        fac[i] = fac[i-1] * i % MOD;
        ifac[i] = ifac[i-1] * inv[i] % MOD;
    }
}

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    int n; string s;
    while (cin >> n >> s) {
        if (n % 2) { cout << 0 << '\n'; continue; }
        int L=0, R=0; bool ok=true;
        for (char ch : s) {
            if (ch == '(') ++L; else ++R;
            if (R > L) { ok=false; break; }
        }
        if (!ok) { cout << 0 << '\n'; continue; }
        int a = n/2 - L, b = n/2 - R;
        if (a > b) swap(a, b);
        long long ans = (C(a+b, a) - C(a+b, a-1) + MOD) % MOD;
        cout << ans << '\n';
    }
    return 0;
}

關鍵點

• 線性預處理逆元 O(MAXN)，單次查詢 O(|str|)。
• 注意 n 為奇數直接輸出 0。
• 前綴合法性檢查：任意前綴 ')' 不得多於 '('。