题解：[CF1924D] Balanced Subsequences

123456xwd · 2024-08-24 11:58:24 · 题解

首先，若 \min(n,m)<k，显然无解。

我们发现，假设我们确定了序列中受匹配的左右括号，整个序列都确定了，你一定是从最左边的空位一直开始填 )，填完后在剩下的空位填写 ( 即可。

那么，\tbinom{n+m}{k} 其实就表示在长度为 n+m 的空串中，选出来 \le k 对合法括号子序列的方案数，相当于我们统计受匹配的左括号，然后就可以确定与之对应的右括号，然后就可以得到整个序列了。

不过由于我们随便放可能导致这 k 个左括号中有的无法填写合法的右括号，所以是 \le k（如左括号填写在最右边的情况）。

所以我们最终的答案就是 \tbinom{n+m}{k}-\tbinom{n+m}{k-1}，就是 \le k 对匹配的减去 \le k-1 对匹配的，其实就是有 k 对匹配的方案数。

代码显然，就不放了。