【排列组合, 卡特兰数】满足条件的01序列

题目

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

---

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

输出的答案对 $10^9+7$ 取模。

输入格式

共一行，包含整数 $n$ 。

输出格式

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

数据范围

$1 \le n \le 10^5$

输入样例：

3

输出样例：

5

解题

方法一：卡特兰数 求组合数 快速幂

思路

转化该问题：

建立一个直角坐标系，从坐标系原点出发，对于 $01$ 序列中的每一个数：

• 如果是 $0$ ，就向右走一格；
• 如果是 $1$ ，就向上走一格。

例如，当前 $n=6$ ，组成了一个 $01$ 序列为：$100110001110$ ：

这样以来我们就把每一个可能的 $01$ 序列映射为了一条从 $(0, 0)$ 走到 $(n, n)$ 的路径（一一对应，不重不漏）。

题目要求序列满足任意前缀序列中 $0$ 的个数都不少于 $1$ 的个数，在图中就表现为：在路径的上的任意一个点的坐标都必须满足 $x > y$ ，也就是说，如图，合法的路径必须保持在红线的右下方（绿线的右下方或压住绿线）：

此时，从 $(0, 0)$ 走到 $(n, n)$ 且不经过红线的路径的个数便是我们要求的答案。直接求没有思路，但是可以通过求出所有从 $(0, 0)$ 走到 $(n, n)$ 的路径的数量再减去非法路径的数量来得到。

所有从 $(0, 0)$ 走到 $(n, n)$ 的路径总数为 $\mathrm{C}_{2n}^n$ （总共要走 $2n$ 步，从中选 $n$ 步向右走）。

如何求经过红线的路径的个数？

对于所有经过红线的路径：

我们把它从第一次与红线相交的点开始的后半部分以红线为轴做轴对称：

此时它的终点一定会落在 $(n-1, n+1)$ 上（因为原终点 $(n, n)$ 按照红线做轴对称后一定会落在 $(n-1, n+1)$ 上）。

我们发现：任何一条从 $(0, 0)$ 走到 $(n, n)$ 且经过红线的非法路径在经过这样的部分轴对称变换后，都会变成一条从 $(0, 0)$ 走到 $(n-1, n+1)$ 的路径（一一对应，不重不漏），那么所有从 $(0, 0)$ 走到 $(n-1, n+1)$ 的路径的数量便是非法路径的数量。

所有从 $(0, 0)$ 走到 $(n-1, n+1)$ 的路径总数为 $\mathrm{C}_{2n}^{n-1}$ （总共要走 $2n$ 步，从中选 $n-1$ 步向右走）或 $\mathrm{C}_{2n}^{n+1}$ （总共要走 $2n$ 步，从中选 $n+1$ 步向上走）。

所有合法路径（合法方案）的数量即为：（卡特兰数）

$$\begin{aligned} \mathrm{C}_{2n}^n - \mathrm{C}_{2n}^{n-1} &= \frac{(2n)!}{n! \cdot n!} - \frac{(2n)!}{(n-1)!(n+1)!} \\ &= \frac{(2n)!(n+1) - (2n)! \cdot n}{n!(n+1)!} \\ &= \frac{(2n)!}{n!(n+1)!} \\ &= \frac{1}{n+1} \cdot \frac{(2n)!}{n! \cdot n!} \\ &= \frac{\mathrm{C}_{2n}^n}{n+1} \end{aligned}$$

$n$ 的范围是 $10^5$ ，直接从定义出发求组合数即可：

$$\mathrm{C}_n^{m} = \frac{n!}{m!(n-m)!} = \frac{\prod_{i=n-m+1}^{n} i}{m!} = \frac{n(n-1) \dots (n - m + 2)(n - m + 1)}{1 \times 2 \times \dots \times m}$$

模数 $10^9 + 7$ 是个质数，所以可以用快速幂求逆元把计算过程中的除法变乘法。

代码

import java.util.*;
import java.io.*;

public class Main {
    static final int MOD = (int) 1e9 + 7;
    
    static long qmi(long base, long exp) {
        long res = 1L;
        while (exp > 0) {
            if ((exp & 1) == 1) res = (res * base) % MOD;
            base = (base * base) % MOD;
            exp >>= 1;
        }
        return res;
    }
    
    static int C(int a, int b) {
        long nume = 1L, deno = 1L;
        for (int i = a, j = 1; j <= b; --i, ++j) {
            nume = nume * i % MOD;
            deno = deno * j % MOD;
        }
        return (int) (nume * qmi(deno, MOD - 2) % MOD);
    }
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        System.out.println(1L * C(2 * n, n) * qmi(n + 1, MOD - 2) % MOD);
    }
}