卡特兰数
问题
给定 $n$ 个 $0$ 和 $n$ 个 $1$,它们将按照某种顺序排成长度为 $2n$ 的序列,求它们能排列成的所有序列中,能够满足任意前缀序列中 $0$ 的个数都不少于 $1$ 的个数的序列有多少个。
输出的答案对 $10^9+7$ 取模。
问题转化
把序列转化为在坐标轴中唯一对应的路径,规定 $0$ 表示向右走一格,$1$ 表示向上走一格。例如下图中,到达 $(6,6)$ 的路径与序列 $011000100111$ 是唯一对应的。
那么假设给定 $x$ 个 $0$ 和 $y$ 个 $1$,那么所有序列的数量就是从 $(0,0)$ 到达 $(x,y)$ 的路径数目,且每一个序列都有唯一的路径与之对应。
如何实现序列的任意前缀中 $0$ 的个数都不少于 $1$ 的个数呢?
只需要保证对于序列中所对应的路径中任意一个点都满足 $x \geq y$,即路径不能经过 $y = x + 1$
例如,假设给定 $6$ 个 $x$ 和 $6$ 个 $y$,那么只要保证到达 $(6,6)$ 的路径中的点都在 $y = x$ 之下(包含 $y = x$),那么该路径对应的序列就是合法的序列。
算法示例
给定 $6$ 个 $1$ 和 $6$ 个 $0$,求符合问题的序列有多少个。
首先我们可以求出总共有 $C_{12}^6$ 种序列,因为在从 $(0,0)$ 到 $(6,6)$ 的路径中,分别 $6$ 次向右走和向上走就能到达 $(6,6)$。
而不符合问题要求的路径就是经过红线的路径。对于任意一条经过红线到达 $(6,6)$ 的路径,我们将第一个经过红线的点后的路径关于红线 $y = x + 1$ 轴对称,总可以将终点对称到 $(5,7)$。因此每一条经过红线的路径都可以与某条到达 $(5,7)$ 的路径唯一对应,即经过红线的路径数目就是从 $(0,0)$ 到达 $(5,7)$ 的路径数目。
从 $(0,0)$ 到达 $(6,6)$ 的路径数目是 $C_{12}^5$ (或 $C_{12}^7$),即 $5$ 次选择向右走, $7$ 次选择向上走。
因此在不经过红线的情况下,到达 $(6,6)$ 的路径数是:
$$C_{12}^6 - C_{12}^5 = 132$$
对于一般情况,假设给定 $n$ 个 $0$ 和 $n$ 个 $1$, 那么合法的序列数是:
$$ \begin{align*} C_{2n}^n - C_{2n}^{n-1} &= \frac{(2n)!}{n!\cdot n!} - \frac{(2n)!}{(n-1)! \cdot (n + 1)!}\\ &= \frac{(n + 1) \cdot (2n)!}{(n + 1)! \cdot n!} - \frac{n \cdot (2n)!}{n! \cdot (n + 1)!}\\ &= \frac{(n + 1) \cdot (2n)! - n \cdot (2n)!}{n! \cdot (n + 1)!}\\ &= \frac{(2n)!}{n! \cdot (n + 1)!}\\ &= \frac{1}{n + 1} \cdot \frac{(2n)!}{n! \cdot n!}\\ &= \frac{1}{n + 1} \cdot C_{2n}^n \end{align*} $$
$C_{2n}^n - C_{2n}^{n-1} = \frac{1}{n + 1} \cdot C_{2n}^n$ 就是卡特兰数,很多问题的方案数就是卡特兰数,例如 火车进站问题,合法括号序列问题。
算法实现
#include<iostream>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
int qmi(int a, int k, int p){
int res = 1;
while(k){
if(k & 1) res = (LL)res * a % p;
a = (LL) a * a % p;
k >>= 1;
}
return res;
}
int main(){
int n;
cin >> n;
int a = 2 * n, b = n;
int res = 1;
for(int i = a;i > a - b;i--) res = (LL)res * i % mod;//计算a! / b!
for(int i = 1;i <= b;i++) res = (LL)res * qmi(i, mod - 2, mod) % mod;//用快速幂求逆元来计算除以b!
res = (LL)res * qmi(n + 1, mod - 2, mod) % mod;//求n + 1的逆元来计算除以(n + 1)
cout << res << endl;
return 0;
}