75.Acwing基础课第889题-简单-满足条件的01序列
题目描述
\(给定 n 个 0 和 n 个 1，它们将按照某种顺序排成长度为 2n 的序列，求它们能排列成的所有序列中，能够满足任意前缀序列中 0 的个数都不少于 1 的个数的序列有多少个\)。
\(输出的答案对 10^9+7 取模\)。
输入格式
\(共一行，包含整数 n\)。
输出格式
\(共一行，包含一个整数，表示答案\)。
数据范围
\(1≤b≤a≤10^5\)
输入样例：
3
输出样例：
5
代码：
// 包含基础输入输出、算法头文件
#include <iostream>
#include <algorithm>using namespace std;// 定义长整型别名：防止乘法过程中溢出int范围（如1e5级别的数相乘）
typedef long long LL;// 常量定义：
// N=100010：预留的常量（本模板未直接使用，适配扩展场景）
// mod=1e9+7：模数（质数，适配费马小定理求逆元）
const int N = 100010, mod = 1e9 + 7;// 快速幂函数：计算 (a^k) mod p 的结果（费马小定理求逆元的核心）
// 参数：a-底数，k-指数，p-模数（本题中p=mod是质数）
int qmi(int a, int k, int p)
{int res = 1; // 初始化结果为1（乘法单位元）// 二进制分解指数k，时间复杂度O(logk)while (k){// k&1：判断k的二进制最低位是否为1（等价于k%2==1）if (k & 1) res = (LL)res * a % p; // 结果乘当前底数，转LL防溢出a = (LL)a * a % p; // 底数平方，转LL防溢出k >>= 1; // 指数右移一位（等价于k /= 2）}return res; // 返回 (a^k) mod p
}int main()
{int n; // n：求第n个卡特兰数cin >> n;// 卡特兰数公式：Catalan(n) = C(2n, n) / (n+1)// 第一步：计算组合数C(2n, n)的分子部分：(2n) * (2n-1) * ... * (n+1)int a = n * 2, b = n; // a=2n（组合数C(2n,n)的总数），b=n（选取数）int res = 1;// 循环b次，计算分子：(2n) * (2n-1) * ... * (2n - n + 1) = (2n)! / n!for (int i = a; i > a - b; i -- ) res = (LL)res * i % mod;// 第二步：除以分母n!（模运算中除法转乘逆元）// 分母是n! = 1*2*...*n，依次乘每个数的逆元for (int i = 1; i <= b; i ++ ) res = (LL)res * qmi(i, mod - 2, mod) % mod;// 第三步：除以(n+1)（卡特兰数公式的最后一步，同样转乘逆元）res = (LL)res * qmi(n + 1, mod - 2, mod) % mod;// 输出第n个卡特兰数 mod 1e9+7的结果cout << res << endl;return 0;
}