题目描述
给定n个0和n个1,它们将按照某种顺序排成长度为2n的序列,求它们能排列成的所有序列中,能够满足任意前缀序列中0的个数都不少于1的个数的序列有多少个。
输出的答案对109+7取模。
输出格式
共一行,包含整数n。
输出格式
共一行,包含一个整数,表示答案。
数据范围
1≤n≤105
算法1
卡特兰数:C[2n][n] - C[2n][n-1] = 1 / n + 1 * C[2n][n];
通过转换为走过的路径得到结果为卡特兰数;
C++ 代码
#include<iostream>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
//快速幂;
int qmi(int a, int k)
{
int res = 1;
while(k)
{
if (k & 1) res = (LL)res * a % mod;
a = (LL) a * a % mod;
k >>= 1;
}
return res;
}
int main()
{
int n;
cin >> n;
int a = 2 * n, b = n;
int res = 1;
for(int i = a, j = 1; j <= b; j ++, i --)
{
res = (LL)res * i % mod;
res = (LL)res * qmi(j, mod - 2) % mod;
}
res = (LL) res * qmi(n + 1, mod - 2) % mod;
cout << res;
return 0;
}