题目描述
给定 n 个 0 和 n 个 1,它们将按照某种顺序排成长度为 2n 的序列,求它们能排列成的所有序列中,能够满足任意前缀序列中 0 的个数都不少于 1 的个数的序列有多少个。
输出的答案对 $10^9+7$ 取模。
输入格式
共一行,包含整数 n。
输出格式
共一行,包含一个整数,表示答案。
数据范围
$1≤n≤10^5$
样例
输入样例:
3
输出样例:
5
算法
卡特兰数
时间复杂度
参考文献
1.案例
三个0三个1
如果要求满足题目条件,则第一个数必须是0,最后一个数必须是1
0 0 0 1 1 1
0 0 1 1 0 1
0 0 1 0 1 1
0 1 0 0 1 1
0 1 0 1 0 1
2.题目分析
如果n等于6,即6个0和6个1
(1)可将题目转化为从原点(0,0)走到终点(6,6)有多少路径的问题
即把每一种数列转化成一种路径
0:向右走一格
1:向上走一格
也就是说 可以把任何一个排列转化成从(0,0)走到(6,6)的路径,
任何一条从(0,0)走到(6,6)的路径都可以转化成一个排列
需要满足:任意前缀序列的 0 的个数都不少于 1 的个数,则 x>=y
即满足条件的路径都不能超过蓝边(可以经过蓝边但是绝对不能经过红边)
3. 问题转化为
从(0,0)到(n,n)不经过红边的所有路径个数:
即总共的方案数 - 经过红边的方案数
总方案数:$C_{2n}^n$
原因:从(0,0)到(6,6)一共需要12步,挑选6步向上走
总方案数为 $C_{12}^6$
经过红颜色边的路径个数:
案例: 0 0 1 1 0 1 1 1 0 0 0 1
对于任何一条经过红颜色边的路径,找到第一个走到红颜色边的点(第一个与红颜色边相交的点),将这条路径从这个点的后半部分关于红颜色边做轴对称,(6,6)的对称点为(5,7)。
即任何经过红颜色边的点都可以使用这种方式,找到第一个走到红颜色边的点,将后面的部分关于红颜色边做轴对称,则终点一定是(5,7)(即(6,6)关于红颜色边的对称点)。
任何一条从(0,0)到(6,6)经过红颜色边的点,通过上述方式都可以变成一条从(0,0)走到(5,7)的路径;而任意一条从(0,0)走到(5,7)的路径都会经过红颜色边,找到第一个经过红颜色边的点,关于红颜色边做轴对称,可以变成一条从(0,0)走到(6,6)并经过红颜色边的路径。
即从(0,0)走到(5,7)的路径与从(0,0)走到(6,6)且经过红颜色边的路径一一对应。
从(0,0)到(5,7)的所有路径为 $C_{12}^5$,则从(0,0)到(6,6)经过红颜色边的路径为$C^5_{12}$
从(0,0)到(6,6)不经过红边的所有路径个数: $C_{12}^6 - C_{12}^5$
进行一般化,从(0,0)到(n,n)不经过红边的所有路径个数: $C_{2n}^n - C_{2n}^{n-1}$
4. 公式化简
即 $C_{2n}^n - C_{2n}^{n-1} = = \frac{1}{(n+1)}\, * \, C_{2n}^n$ (卡特兰数)
C++ 代码
#include <iostream>
#include <algorithm>
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;
k >>= 1;
a = (LL)a * a % p;
}
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;
for (int i=1; i<=b; i++) res = (LL) res * qmi(i, mod-2, mod) % mod;
res = (LL) res * qmi(n+1, mod-2, mod) % mod;
cout<<res<<endl;
return 0;
}
好题解没人点赞系列