本文共 1368 字，大约阅读时间需要 4 分钟。

题目链接:

时/空限制：1s / 64MB

题目描述

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

输出的答案对109+7取模。

输出格式

共一行，包含整数n。

输出格式

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

数据范围

1≤n≤10^5

输入样例

3

输出样例

5

解题思路

题意:求任意前缀序列中0的个数都不少于1的个数的序列有多少个。

思路:卡特兰数裸题，在2n位序列中填入n个0的方案数为C(2n,n)，不填0的其余n位自动填1。从中减去不符合要求(由左而右扫描，1的累计数大于0的累计数)的方案数即为所求。

    不符合要求的数的特征是由左而右扫描时，必然在某一奇数位2m+1位上首先出现m个0的累计数和m+1个1的累计数，此后的2(n-m)-1位上有n-m个0和n-m-1个1。如若把后面这2(n-m)-1位上的0和1互换，使之成为n-m-1个0和n-m个1，结果得到一个由n-1个0和n+1个1组成的2n位序列，即一个不合要求的数对应于一个由n-1个0和n+1个1组成的排列。

    反过来，任何一个由n-1个0和n+1个1组成的2n位序列，由于0的个数少2个，2n为偶数，所以必定在某一个奇数位上出现1的累计数超过0的累计数。同样在后面部分0和1互换，使之成为由n个0和n个1组成的2n位序列，即n-1个0和n+1个1组成的2n位序列必对应一个不符合要求的数。

因而不合要求的2n位序列与n-1个0，n+1个1组成的序列一一对应。

显然，不符合要求的方案数为C(2n,n-1)。由此得出输出序列的总数目为：

，也就是卡特兰数。

Accepted Code:

/*  * @Author: lzyws739307453  * @Language: C++  */#include 
   
    using namespace std;typedef long long ll;const int MOD = 1e9 + 7;int Fast_Power(int a, int b, int p) {    int res = 1;    while (b) {        if (b & 1)            res = 1ll * res * a % p;        a = 1ll * a * a % p;        b >>= 1;    }    return res;}int Com_Num(int a, int b, int p) {    int res = 1;    for (int i = 1, j = a; i <= b; i++, j--)        res = 1ll * res * j % p * Fast_Power(i, p - 2, p) % p;    return res;}int main() {    int n;    scanf("%d", &n);    printf("%d\n", 1ll * Com_Num(n << 1, n, MOD) * Fast_Power(n + 1, MOD - 2, MOD) % MOD);    return 0;}
   

转载地址：http://wybtf.baihongyu.com/