卡特兰数

结论

卡特兰数.pdf

889. 满足条件的01序列
给定 n 个 0 和 n 个 1，它们将按照某种顺序排成长度为 2n 的序列，求它们能排列成的所有序列中，能够满足任意前缀序列中 0 的个数都不少于 1 的个数的序列有多少个。
输出的答案对 109+7 取模。
输入格式
共一行，包含整数 n。
输出格式
共一行，包含一个整数，表示答案。
数据范围
1≤n≤1051≤n≤105
输入样例：

3

输出样例：

5

import java.util.*;
public class Main {
    static final int MOD = 1000000007;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a = 2 * n, b = n;
        int res = 1;
        for (int i = a; i > b; i--) {
            res = (int)(1L * res * i % MOD);
        }
        for (int i = 2; i <= b; i++) {
            res = (int)(1L * res * qmi(i, MOD - 2, MOD) % MOD);
        }
        res = (int)(1L * res * qmi(n + 1, MOD - 2, MOD) % MOD);
        System.out.println(res);
    }
    static int qmi(long a, int b, int p) {
        long res = 1;
        while (b > 0) {
            if ((b & 1) == 1) {
                res = res * a % p;
            }
            a = a * a % p;
            b >>= 1;
        }
        return (int)res;
    }
}

类似的问题

1. 一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列?
2. 有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少种方法使得只要有10元的人买票，售票处就有5元的钞票找零？
3. 矩阵连乘： P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案。
4. n个0和n个1组成一个2n位的2进制数，要求从左到右扫描时，1的累计数始终都小于等于0的累计数，求满足条件的数有多少？ | 模型 | 事件1 | 事件2 | | —- | —- | —- | | (1) | 入栈 | 出栈 | | (2) | 用5元支付 | 用10元支付 | | (3) | 左括号 | 右括号 | | (4） | 0 | 1 |

事件1一定在事件2之前发生，换句话说，每个事件2发生前一定有一个事件1发生

1. 多边形三角划分的方案数

1. n个相同点构成的不同二叉树的数量