组合数学例题：Codeforces#round404 - D(785D)

组合数学 算法

---

主页地址 ：月光森林

---

仍然任性地践行不写题解的原则，于是默默地把标题改成了组合数学例题。但是实际上还是一篇题解，大家就默默地看不要吐槽就好。

OK， link start：

题目描述

先给出原题链接 ： codeforces#Round404(div-2)-D

一个RSBS（标准简式括号表达式）是指一个只包含'(' 和 ')' 的长度为n的字符串，且满足一下条件：

• 非空（即 $n\neq 0$ ）
• 长度是偶数（即 $n \% 2 = 0$）
• 前 $\frac n 2$ 个字符都是 '('
• 后 $\frac n 2$ 个字符都是 ')'

现在给定一个长度为 $n (1 \leq n \leq 200,000)$ 的括号表达式 s ，问 s 中有多少个子串是 RSBS。

所谓子串是指删掉 s 中的一些字符得到的串。所以题目实际上是在问有多少种删除字符的方式可以获得一个RSBS， 或者说是从原串 s 中选择出一定字符可以组成一个RSBS的不同方法。

解题思路

假如 s 串中一共有 m 个左括号，则可以将从 s 中得到的RSBS作 m 个划分， 每个划分是以第 i （$1 \leq i \leq m$）个左括号为中心得到的RSBS。

因此，可以以左括号（"("）的位置作为枚举对象。

假设对于某个位置处的左括号，它左边有 $p$ 个左括号，右边有 $q$ 个右括号, 则对于这个确定的左括号来说， 以它为中心的得到的RSBS的数量满足：

$$ans = \sum^{min(p, q)}_{k = 0}\begin{pmatrix} p \\ k \end{pmatrix} * \begin{pmatrix} q \\ k + 1 \end{pmatrix}$$

对于这个公式，实际上可以化简 ，直接上结论:

$$ans = \sum^{min(p, q)}_{k = 1}\begin{pmatrix} p \\ k \end{pmatrix} * \begin{pmatrix} q \\ q - k - 1 \end{pmatrix} = \begin{pmatrix} p + q \\ q - 1 \end{pmatrix}$$

这相当于连续摆放的 $p + q$ 个物品，从中选取 $q - 1$ 个物品。

这个题目的难点就在于化简，比赛当时想到了这个思路和公式，但就是想不出来怎么化简。比赛结束看讨论才知道的：

而如何计算组合数，可以从本人之前的博客查看，根据数据范围，这个地方使用的是公式法+逆元。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL maxn(2e5 + 5);
char bct[maxn];
int r[maxn], n; // r[]数组记录右括号的数量
/******** 计算C(n, m) 的算法********/
const LL mod(1e9 + 7);
LL jC[maxn];
LL niY(LL t)
{
    LL p = mod - 2, res = 1;
    while(p)
    {
        if(p & 1) res = res * t % mod;
        t = t * t % mod;
        p >>= 1;
    }
    return res;
}
void init()
{
    jC[0] = jC[1] = 1;
    for(int i = 2; i < maxn; i++)
        jC[i] = jC[i - 1] * i % mod;
}
LL calC(LL n, LL m)
{
    LL ma = niY(jC[m]) * niY(jC[n - m]) % mod;
    return (jC[n] * ma % mod) % mod;
}
/******** 计算C(n, m) 的算法********/
int main()
{
    init();
    //freopen("data.in", "r", stdin);
    while(~scanf("%s", bct))
    {
        n = strlen(bct);
        r[n] = 0;
        for(int i = n - 1; i >= 0; i--)
            r[i] = bct[i] == ')' ? r[i + 1] + 1 : r[i + 1];
        LL ans = 0;
        for(int i = 0, j = 0; i < n; i++)
            if(bct[i] == '(')
            {
                ans = ans + calC(j + r[i], r[i] - 1);
                ans %= mod, j ++;
            }
        printf("%I64d\n", ans);
    }
    return 0;
}

以上です～