【CF1924D】Balanced Subsequences 【卡特兰数，组合数，数学】

本文主要是介绍【CF1924D】Balanced Subsequences 【卡特兰数，组合数，数学】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

$CF 1924 D .$ Balanced Subsequences

题意为：给定 $n, m, k$ ，求有多少个由 $n$ 个 (， $m$ 个 ) 组成的序列满足最长的合法括号子序列的长度恰为 $2 k$ （对 $10^9+7$ 取模）。

思路

我们很容易想到这跟 $C a t e l an$ 数有关。

首先我们知道：长度为 $2 k$ 的合法括号序列包含 $k$ 个左括号和 $k$ 右括号。

首先有 $k>\min\{n,m\}$ ，则不合法。

我们现在由 $n - k$ 个废物左括号，和 $m - k$ 个废物右括号。

不难想出，肯定把废物右括号放在废物左括号前，以免它们再从产生新的贡献。

将括号序列抽象成折线，初始位置在 $(0, 0)$ ， $x$ 轴表示当前括号的总数，而 $y$ 轴表示左括号 $-$ 右括号，也就是说，折线只能往右上或者右下走。

而我们有 $m - k$ 个废物右括号会失配，所以最终在某一横坐标下，纵坐标会到达 $k - m$ ，因为当废物右括号失配时，前面的括号肯定全部匹配完毕了。

而我们最终要到达的坐标为 $(n + m, n - m) .$

题意转换为：从 $(0, 0)$ 到 $(n + m, n - m)$ 的合法路径（合法判定为：路径不越过 $y = k - m$ 的路径（为什么是 $y = k - m$ ，因为后面 $m - k$ 都是没用的，所以不能合用，此为达到 $k$ 的基础））。

我们不难想到用容斥原理：而减去部分就为 $(0,0)\rightarrow(n+m,2 \times k - n - m)$ ，其方案数不难得出为： $C_{n+m}^{k-1}$

所以 $ans=C_{n+m}^{k}-C_{n+m}^{k-1}.$

我们就有了一下代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long
#define N 5006
using namespace std;
const int mod = 1e9+7;
int n,m,jc[N],k;
int qpow(int a,int b) {int res = 1;while (b) {if (b & 1) res = res * a % mod;a = a * a % mod;b >>= 1;}return res;
}
int C(int a,int b) {if (a < 0 || b < 0 || a < b) return 0;return jc[a] * qpow(jc[b] * jc[a - b] % mod,mod - 2) % mod;
}
signed main(){int T;jc[0] = 1;for (int i = 1;i <= 5000;i ++) jc[i] = jc[i - 1] * i % mod;cin >> T;for (;T--;) {scanf("%lld%lld%lld",&n,&m,&k);if (min(n,m) < k) printf("0\n");else printf("%lld\n",(C(n + m,k) - C(n + m,k - 1) + 2 * mod) % mod);} 
//	cout << (C(n + m,n) - C(n + m,n + 1) + 2 * mod) % mod;return 0;
}