这不是我们括号串原题吗，下次记得注明出处

UnyieldingTrilobite · 2024-01-28 14:56:07 · 题解

场上看到这玩意直接傻了。不止在一个地方见过这个形式。

我们考虑对一个固定的字符串，存在贪心算法求它的最长合法子序列。维护一个初始为空的栈并从左到右扫描每一个括号，若为左括号则入栈，若为右括号且栈非空则弹栈并更新答案。若不妨 n\ge m，则要考虑的仅仅是有多少个右括号入栈时栈为空。考虑维护一条折线，从 (0,0) 到 (n+m,n-m)；随着横坐标的增大，纵坐标依照横坐标对应下标的括号而变化：若为左括号则增一，否则减一。那么不难发现，当有右括号无法入栈时，本质上是折线当前落点在横轴上，将减一的折线修正为与横轴贴合。如此一来，所有该位置之后的折线全体向上平移一格。以此视角来看，右括号入栈时栈为空的次数恰等于折线所能达到最低点的纵坐标的绝对值。换而言之，折线能达到的最低点纵坐标为 k-m。

由于折线起始点在 (0,0)，所以一旦 k\gt m 则会直接矛盾。否则，我们本质上是要统计这样折线的数量：从 (0,0) 到 (n+m,n-m)，且最低点纵坐标为 k-m。我们意识到这玩意不太好做。记 f(t) 为从 (0,0) 到 (n+m,n-m)，且最低点纵坐标不大于 t-m 的数量，那么答案显然为 f(k)-f(k-1)。熟悉卡特兰数的话这里就很典了，把折线最后一次触碰直线 y=t-m 的交点之后的部分全部上下反转，那么这就成为了一条从 (0,0) 到 (n+m,2t-n-m) 的折线，方案数显然等于 \binom{n+m}{t}。

于是这个题就做完了。代码丢个核心部分吧。

  for (cin >> T; T; --T) {
    cin >> n >> m >> k;
    if (k > min(n, m)) {
      cout << 0 << '\n';
      continue;
    }
    cout << (C(n + m, k) - C(n + m, k - 1)).val() << '\n';
  }