java---卡特兰数---满足条件的01序列（每日一道算法2022.9.29）

注意事项：
涉及到快速幂求逆元的使用:java—快速幂—求逆元

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

输出的答案对 109+7 取模
1 ≤ n ≤ 10^5

输入:
3

输出：
5

public class 求组合数_5_卡特兰数_01序列 {
    public static int mod = 1000000007;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), a = n*2, b = n;

        //这里就是根据组合数的公式直接推出答案，在lucas定理那也用过
        long res = C(a, b);

        //根据公式，乘上n+1的逆元
        res = res * qmi(n+1, mod-2, mod) % mod;

        System.out.println(res);
    }

    //根据公式直接推
    //举个栗子，C62，从6中选2，也就是6!/2!(6-2)! = 6*5/2*1, 我们不想计算除法，直接用乘法逆元代替，res*6*逆(1)*5*逆(2)
    public static long C(int a, int b) {
        long res = 1;
        for (int i = 1, j = a; i <= b; i++, j--) {
            res = res * j % mod;
            res = res * qmi(i, mod-2, mod) % mod;
        }
        return res;
    }

    //快速幂
    public static int qmi(int a, int k ,int p) {
        long res = 1;
        while (k > 0) {
            if ((k&1) == 1) res = res*a % p;
            k >>= 1;
            a = (int)((long)a*a % p);
        }
        return (int)res;
    }
}

卡特兰数思路：
(番茄酱大佬思路写的太清晰了，我就直接搬过来了，源地址：AcWing 889. 满足条件的01序列)

将 0101 序列置于坐标系中，起点定于原点。若 00表示向右走，1表示向上走，那么任何前缀中 0 的个数不少于 1 的个数就转化为，路径上的任意一点，横坐标大于等于纵坐标。题目所求即为这样的合法路径数量

下图中，表示从 (0,0)走到 (n,n)的路径，在绿线及以下表示合法，若触碰红线即不合法

声明：算法思路来源为y总，详细请见https://www.acwing.com/
本文仅用作学习记录和交流