原题大意

给出一组由“（”和“)”组成的字符串，问有多少种方法使得删除其中一些括号后，字符串会成为RSBS串，RSBS串是一种左右完全对称的串，如“（（（）））”，有一些则不是，如“（（（））”，“（（）（））”。

算法分析

删除几个，其实也就是算有几种成立。看了网上的代码，知道了如何通过逆元来算组合数，博客如下，本题中求1/(k!) 是通过 k^(MOD - 2) % MOD (MOD为素数);

程序代码

#include <cstdio>
#include <memory.h>
#include <cstring>
using namespace std;
typedef long long LL;
const int maxn = 2e5+5;
const LL mod = 1e9 + 7;

int n;
char s[maxn];
int l[maxn], r[maxn];
LL fac[maxn], inv[maxn];//fac[i] 保存阶乘，inv[i] 保存fac[i]的逆元

void add(LL &a, LL b){
    a += b;
    if(a >= mod) a -= mod;
}

//快速幂
LL pow_mod(LL a, LL p){
    LL ans = 1;
    while(p){
        if(p & 1) ans = ans * a % mod;
        a = a * a % mod;
        p >>= 1;
    }
    return ans;
}

//组合计算公式
LL C(int n, int k){
    return (fac[n] * inv[k] % mod )* inv[n-k] % mod;
}


int main(){
    fac[0] = 1;
    for(int i = 1; i < maxn; i++) fac[i] = fac[i-1] * i % mod;
    inv[maxn - 1] = pow_mod(fac[maxn - 1], mod - 2);
    for(int i = maxn - 2; i >=0; i--) inv[i] = inv[i+1] * (i+1) % mod;
    while(~scanf("%s", s+1)){
        memset(l,0,sizeof(l));
        memset(r,0,sizeof(r));
        n = strlen(s+1);
        for(int i = 1; i <= n; i++) l[i] = l[i-1] + (s[i] == '(');
        for(int i = n; i >= 1; i--) r[i] = r[i+1] + (s[i] == ')');
        LL ans = 0;
        for(int i = 1; i <= n; i++)
            if(s[i] == '(')
            add(ans, C(((l[i] + r[i]) % mod + mod - 1) % mod, l[i]));
        printf("%lld\n", ans);    

    }
    return 0;
}