主要知识点

1. 范德蒙恒等式

\(\sum_{i=0}^kC_m^iC_n^{k-i}=C_{m+n}^k\)

证明：

考虑生成函数\(g(x) = (1+x)^{n+m}\)

对于其k次项，如果二项式直接展开，得到k次项系数为\(C_{n+m}^k\)

而将他拆开为\((1+x)^n*(1+x)^m\)再二项式展开，得到k次项系数为\(\sum_{i=0}^k C_{m}^iC_n^{k-i}\)

证毕！

2.线性求逆元

目标:1~n中每个数关于p的逆元。

1. 首先inv(1) = 1恒成立。

2. 对于i>1，对p拆分，p=ki+j，其中k = p // i，j = p % i。（//为整除，%为模运算）

   那么

   \[ki+j\equiv0\pmod p \]

   两边同乘inv(i)*inv(j)可以推出

   \[-k*inv(j)\equiv inv(i)\pmod p \]
   \[inv(i)\equiv (p - p//i)*inv(p\%i) \pmod p \]

   由上可以O(n)递推。

题面

读入一个括号序列，问有多少个子序列满足完美括号匹配？

子序列指任意取。

完美括号匹配指的是左括号全在左边，右括号全在右边，并且匹配。

算法

首先的想法是我们扫描序列，对于每个左括号，我们将它强制为最内层左括号，计算左边右边选括号进行匹配的总数。

这样好办，从头到尾记录左括号前缀和l[]，从后往前记录右括号后缀和r[]，然后扫描每个左括号，加入答案。

而每个左括号的贡献就是

\[\sum_{i=0}^{min(l,r-1)}C_l^i*C_{r}^{i+1} \]

通过范德蒙恒等式和预处理阶乘以及阶乘逆元可以O(1)处理。

\[\sum_{i=0}^{min(l,r-1)}C_l^i*C_{r}^{r-1-i}=C_{l+r}^{r-1} \]

代码

#include 
using namespace std;
string s;
int l[200010], r[200010];
#define LL long long
const LL MOD = 1e9 + 7;
LL fac[200010], fac_inv[200010], inv[200010];
int main()
{
    cin >> s;
    int n = s.size();
    fac[0] = 1;
    for (int i = 1; i <= n; ++i)
        fac[i] = fac[i - 1] * i % MOD;
    inv[1] = 1;
    for (int i = 2; i <= n; ++i)
        inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
    fac_inv[0] = 1;
    for (int i = 1; i <= n; ++i)
        fac_inv[i] = fac_inv[i - 1] * inv[i] % MOD;
    int cnt = 0;
    for (int i = 0; s[i]; ++i)
    {
        l[i] = cnt;
        if (s[i] == '(')
            ++cnt;
    }
    cnt = 0;
    for (int i = n - 1; i >= 0; --i)
    {
        r[i] = cnt;
        if (s[i] == ')')
            ++cnt;
    }
    LL ans = 0;
    for (int i = 0; r[i] >= 1; ++i)
    {
        if (s[i] == ')')
            continue;
        ans = (ans + fac[l[i] + r[i]] * fac_inv[r[i] - 1] % MOD * fac_inv[l[i] + 1]) % MOD;
    }
    cout << ans << endl;
    return 0;
}