当前位置：首页 > news >正文

题解：AcWing 889 满足条件的01序列

news 2026/5/12 18:30:30

【题目来源】

AcWing：889. 满足条件的01序列 - AcWing题库

【题目描述】

给定 \(n\) 个 \(0\) 和 \(n\) 个 \(1\)，它们将按照某种顺序排成长度为 \(2n\) 的序列，求它们能排列成的所有序列中，能够满足任意前缀序列中 \(0\) 的个数都不少于 \(1\) 的个数的序列有多少个。

输出的答案对 \(10^9+7\) 取模。

【输入】

共一行，包含整数 \(n\)。

【输出】

共一行，包含一个整数，表示答案。

【输入样例】

【输出样例】

【解题思路】

【算法标签】

《AcWing 889 满足条件的01序列》 #组合数学# #组合计数# #卡特兰数# #逆元# #快速幂# #费马小定理#

【代码详解】

#include <bits/stdc++.h>
using namespace std;typedef long long LL; // 定义 LL 为 long long 类型
const int N = 100005, mod = 1e9 + 7; // 定义常量 N 和 mod
LL infact[N]; // infact 数组存储阶乘的逆元// 快速幂函数，计算 a^b % p
int qmi(int a, int b, int p)
{int res = 1; // 初始化结果为 1while (b > 0) { // 当 b 大于 0 时循环if (b & 1) res = (LL)res * a % p; // 如果 b 的最低位为 1，更新结果a = (LL)a * a % p; // 更新 ab >>= 1; // 右移 b}return res; // 返回结果
}int main()
{int n; // 定义整数 ncin >> n; // 输入整数 nint res = 1; // 初始化结果为 1// 计算 (2n)! / (n+1)! / n! 的模数for (int i = 2 * n; i > n; i--) res = (LL)res * i % mod; // 计算 (2n)! / n! 的模数infact[0] = 1; // 初始化 infact[0] 为 1for (int i = 1; i <= n; i++) // 计算 1 到 n 的阶乘逆元infact[i] = infact[i - 1] * qmi(i, mod - 2, mod) % mod; // 递推计算阶乘逆元res = (LL)res * infact[n] % mod; // 计算 (2n)! / (n+1)! / n! 的模数res = (LL)res * qmi(n + 1, mod - 2, mod) % mod; // 除以 (n+1) 的模数cout << res << endl; // 输出结果return 0; // 程序结束
}

【运行结果】