侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

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

GabrielxD
2023-03-22 / 0 评论 / 0 点赞 / 189 阅读 / 1,374 字
温馨提示:
本文最后更新于 2023-03-22,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

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


给定 nn00nn11 ,它们将按照某种顺序排成长度为 2n2n 的序列,求它们能排列成的所有序列中,能够满足任意前缀序列中 00 的个数都不少于 11 的个数的序列有多少个。

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

输入格式

共一行,包含整数 nn

输出格式

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

数据范围

1n1051 \le n \le 10^5

输入样例:

3

输出样例:

5

解题

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

思路

转化该问题:

建立一个直角坐标系,从坐标系原点出发,对于 0101 序列中的每一个数:

  • 如果是 00 ,就向右走一格;
  • 如果是 11 ,就向上走一格。

例如,当前 n=6n=6 ,组成了一个 0101 序列为:100110001110100110001110

卡特兰数.gif

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

题目要求序列满足任意前缀序列中 00 的个数都不少于 11 的个数,在图中就表现为:在路径的上的任意一个点的坐标都必须满足 x>yx > y ,也就是说,如图,合法的路径必须保持在红线的右下方(绿线的右下方或压住绿线):

image-20230322164640464

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

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

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

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

image-20230322165845526

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

image-20230322170018046

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

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

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

所有合法路径(合法方案)的数量即为:(卡特兰数

C2nnC2nn1=(2n)!n!n!(2n)!(n1)!(n+1)!=(2n)!(n+1)(2n)!nn!(n+1)!=(2n)!n!(n+1)!=1n+1(2n)!n!n!=C2nnn+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}

nn 的范围是 10510^5 ,直接从定义出发求组合数即可:

Cnm=n!m!(nm)!=i=nm+1nim!=n(n1)(nm+2)(nm+1)1×2××m\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}

模数 109+710^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);
    }
}
0
博主关闭了所有页面的评论