「HDU 5184」Brackets

题目链接:HDU 5184

Description

给你长度为$n$的括号序列的前若干项,请你计算有多少个合法的括号序列。

答案对$10^9+7$取模

Data Range

$n\leq 1000000$

Solution

因为左括号一定是时时刻刻大于等于右括号的数量,那么我们可以把问题转变成在坐标系中的路径统计问题。

具体的就是:我们现在已经有了$a$个左括号和$b$个右括号,也就是意味着我们现在$(a,b)$这个点上,我们需要到$(\frac n2,\frac n2)$这个点上,不能穿过$y=x$的合法方案数。

合法方案数就是总方案数-不合法方案数。

那么这个就是卡特兰数的其中一个应用。

因为我们一定会经过$(i,i+1)$这个上面的点,那么原来的终点不变,是$(\frac n2,\frac n2)$,那么任何一条不合法路径一定会走到$(\frac n2,\frac n2)$关于$y=x+1$对称的点,假设原来我们走的是一个$q\times p$的矩阵,那么翻转上去后,就是一个$(q-1)\times (p+1)$的矩阵,原来的总方案数就是$C_{p+q}^{q}$,现在不合法的方案数就是$C_{p+q}^{q-1}$。

因为数据范围比较大,所以先预处理逆元求组合数。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000000 + 5; 
const int P = 1e9 + 7;
template <typename T> T qpow(T x, T y) {
  T res = 1;
  for (; y; y >>= 1, x = (ll) x * x % P) {
    if (y & 1) res = (ll) res * x % P; 
  }
  return res;
}
template <typename T> void dec(T &x, T y) {
  x = x - y < 0 ? x - y + P : x - y; 
}
template <typename T> void pls(T &x, T y) {
  x = x + y >= P ? x + y - P : x + y; 
}
int n;
ll fac[N], fac_inv[N];
char s[N];
void init() {
  fac[0] = 1; 
  for (int i = 1; i < N; i ++) {
    fac[i] = fac[i - 1] * i % P;
  }
  fac_inv[N - 1] = qpow(fac[N - 1], (ll)P - 2);
  for (int i = N - 2; i >= 0; i --) {
    fac_inv[i] = fac_inv[i + 1] * (i + 1) % P;
  }
}
ll C(ll n, ll m) {
  return fac[n] * fac_inv[m] % P * fac_inv[n - m] % P;
}
int main() {
  init();
  while (~scanf("%d", &n)) {
    scanf("%s", s);
    if (n & 1) {
      puts("0");
      continue;
    }
    else {
      int len = strlen(s), a = 0, b = 0; 
      for (int i = 0; i < len; i ++) {
        if (s[i] == '(') ++ a;
        else ++ b; 
        if (a < b) {
          break;
        }
      }
      if (a < b) {
        puts("0");
        continue;
      }
      int p = n / 2 - a, q = n / 2 - b;
      if (p < 0 || q < 0) {
        printf("0\n");
        continue;
      }
      ll ans = C(q + p, q);
      dec(ans, C(q + p, p - 1));
      printf("%lld\n", ans);
    }
  }
  return 0; 
} 
最后修改:2019 年 08 月 04 日 02 : 30 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论