Leetcode 第 374 场双周赛 Problem D 100146. 统计感冒序列的数目（组合数学+阶乘+逆元）

本文介绍: Lee t code 第 374 场双周赛 Pro ble m D 100146. 统计感冒序列的数目（组合数学+阶乘+逆元）题目给你一个整数 n 和一个下标从 0 开始的整数数组 si c k ，数组按升序排序。有 n 位小朋友站成一排，按顺序编号为 0 到 n – 1 。数组 si c k 包含一开始得了感冒的小朋友的位置。如果位置为 i 的小朋友得了感冒，他会传染给下标为 i – 1 或者 i + 1 的小朋友，前提是被传染的小朋友存在且还没有得感冒。每一秒中，至多一位还没感冒的小朋友会被传染。

Lee t code 第 374 场双周赛 Pro ble m D 100146. 统计感冒序列的数目（组合数学+阶乘+逆元）
题目
- 给你一个整数 n 和一个下标从 0 开始的整数数组 si c k ，数组按升序排序。
- 有 n 位小朋友站成一排，按顺序编号为 0 到 n – 1 。数组 si c k 包含一开始得了感冒的小朋友的位置。如果位置为 i 的小朋友得了感冒，他会传染给下标为 i – 1 或者 i + 1 的小朋友，前提是被传染的小朋友存在且还没有得感冒。每一秒中， 至多一位 还没感冒的小朋友会被传染。
- 经过有限的秒数后，队列中所有小朋友都会感冒。感冒序列指的是所有一开始没有感冒的小朋友最后得感冒的顺序序列。请你返回所有感冒序列的数目。
- 由于答案可能很大，请你将答案对 10 ^ 9 + 7 取余后返回。
- 注意，感冒序列不包含一开始就得了感冒的小朋友的下标。
- 2 <= n <= 10 ^ 5
- 1 <= si c k.length <= n – 1
- 0 <= si c k[i] <= n – 1
- si c k 按升序排列。
示例
- 示例 1：
- 输入：n = 5, si ck = [0,4]
- 输出：4
  - 感冒序列 [1,2,3] ，被传染的顺序：[0,1,2,3,4] => [0,1,2,3,4] => [0,1,2,3,4] => [0,1,2,3,4]
  - 感冒序列 [1,3,2] ，被传染的顺序：[0,1,2,3,4] => [0,1,2,3,4] => [0,1,2,3,4] => [0,1,2,3,4]
  - 感冒序列 [3,1,2] ，被传染的顺序：[0,1,2,3,4] => [0,1,2,3,4] => [0,1,2,3,4] => [0,1,2,3,4]
  - 感冒序列 [3,2,1] ，被传染的顺序：[0,1,2,3,4] => [0,1,2,3,4] => [0,1,2,3,4] => [0,1,2,3,4]
- 示例 2：
- 输入：n = 4, si ck = [1]
- 输出：3
  - 感冒序列 [0,2,3] ，被传染的顺序：[0,1,2,3] => [0,1,2,3] => [0,1,2,3] => [0,1,2,3]
  - 感冒序列 [2,0,3] ，被传染的顺序：[0,1,2,3] => [0,1,2,3] => [0,1,2,3] => [0,1,2,3]
  - 感冒序列 [2,3,0] ，被传染的顺序：[0,1,2,3] => [0,1,2,3] => [0,1,2,3] => [0,1,2,3]
解法
- 组合数学+阶乘+逆元：
- 第 1 步：
- 分析题目易得每秒都 有且仅仅有一位未感冒者 被传染，且他的左或右一定有感冒的人，
- 然后观察示例可以想到：未感冒者会组成 k 个连续区间，除了第一段以及看最后一段区间，中间区间全是左右均有感冒
- 第 2 步：
- 因为已感冒者无法被影响，因此先在区间内部考虑，再思考区间与区间的关系，
- 第 3 步：
- 区间内部的方案数：
  - 第一段或者最后一段仅有 1 种方案数，从右到左与从左到右
  - 中间区间 pre[i] 个人、方案数为：2 ^ (pre[i]-1)
    - 暴力枚举也可
    - DP 也行：dp[i] 代表 i 个人方案数由 i-1 个人方案数选首/尾，且最后一个人无法选择：dp[i] = dp[i-1] * 2
- 第 4 步：
- 每段区间方案数相乘即 总方案数：1 * 2 ^（per[1]-1 + … + per[k-1]-1）* 1
- 但这仅是以整个区间来考虑的，如果形如：pre[0] 中选第一个、pre[2] 中选最后一个、pre[1] 中选第一个…
- 我们将其称为排列数，
- 第 5 步：
- 排序数：sum！/(per0!*per1!*…*perk!)
- 设 pre[i] 总和为 sum，每个区间 per[i] 只有 1 种排序方式（从前到后顺序放入），而区间内部如何选由方案数决定，
- 接着我们又两种思考方式（公式化简后可以互相转化）
  1. 先不管 per 顺序、仅看 sum 的总排序数为 sum!，每种 per 的总排序数 per! 变成 1 种排序方式，结果就是：su m！/ (per0! * pe r1! * … * pe rk!)
  2. 从 s 个空位中找到 pe r[0] 个位置顺序放入、结果为 C（s, pe r[0]），接着从 s–per[0] 个空位找 per[1] 个位置顺序放入、结果为 C（s–per[0], p er[1]） … ,
- 总结果就是 C（s, p er[0]）* C（s-per[0], per[1]) * … * C（s-per[0]-…-per[k-1], per[k]）（可以化简为 su m！/ (per[0]! * per[1]! * … * per[k]!)）
- 第 6 步：
- 结果就是：每种区间内部方案数 * 区间之间的排列数
代码

/**
     * 组合数学+阶乘+逆元：
     *
     * 第 1 步：
     * 分析题目易得每秒都 **有且仅仅有一位未感冒者** 被传染，且他的左或右一定有感冒的人，
     * 然后观察示例可以想到：未感冒者会组成 k 个连续区间，除了第一段以及看最后一段区间，中间区间全是左右均有感冒
     *
     * 第 2 步：
     * 因为已感冒者无法被影响，因此先在区间内部考虑，再思考区间与区间的关系，
     *
     * 第 3 步：
     * 区间内部的方案数：
     *     * 第一段或者最后一段仅有 1 种方案数，从右到左与从左到右
     *     * 中间区间 pre[i] 个人、方案数为：2 ^ (pre[i]-1)
     *         * 暴力枚举也可
     *         * DP 也行：dp[i] 代表 i 个人方案数由 i-1 个人方案数选 首/尾，且最后一个人无法选择：dp[i] = dp[i-1] * 2
     *
     * **第 4 步**：
     * 每段区间方案数相乘即 **总方案数**：1 * 2 ^（per[1]-1 + ... + per[k-1]-1）* 1
     * 但这仅是以整个区间来考虑的，如果形如：pre[0] 中选第一个、pre[2] 中选最后一个、pre[1] 中选第一个...
     * 我们将其称为排列数，
     *
     * **第 5 步**：
     * 排序数：sum！/(per0!*per1!*...*perk!)
     * 设 pre[i] 总和为 sum，每个区间 per[i] 只有 1 种排序方式（从前到后顺序放入），而区间内部如何选由方案数决定，
     * 接着我们又两种思考方式（公式化简后可以互相转化）
     *     1. 先不管 per 顺序、仅看 sum 的总排序数为 sum!，每种 per 的总排序数 per! 变成 1 种排序方式，结果就是：sum！/(per0!*per1!*...*perk!)
     *     2. 从 s 个空位中找到 per[0] 个位置顺序放入、结果为 C(s,per[0])，接着从 s-per[0] 个空位找 per[1] 个位置顺序放入、结果为 C(s-per[0],per[1]) ... ,
     *     总结果就是 C(s,per[0])*C(s-per[0],per[1])*...*C(s-per[0]-...-per[k-1],per[k])（可以化简为 sum！/(per[0]!*per[1]!*...*per[k]!)）
     *
     * 第 6 步：
     * 结果就是：每种区间内部方案数 * 区间之间的排列数
     *
     */
    public int numberOfSequence(int n, int[] sick) {
        long res = 1;

        // 排序数：sum！
        long perTotal = FAC[n - sick.length];

        // 排序数：per[0]，代表第一个感冒左边多少个人
        int per = sick[0];
        perTotal *= INV_FAC[per];
        perTotal %= MOD;

        // 每段区间方案数相乘即 **总方案数**：1 * 2 ^（per[1]-1 + ... + per[k-1]-1）* 1
        int ansPow = 0;

        for (int i = 1; i < sick.length; i++) {
            // 排序数：sum！/(per0!*per1!*...*perk!)
            per = sick[i] - sick[i - 1] - 1;
            perTotal *= INV_FAC[per];
            perTotal %= MOD;

            // 中间的未感冒者有 2 ^ (per-1) 种方案数
            if (per > 0) {
                ansPow += per - 1;
            }
        }

        // 排序数：per[k]，代表最后一个感冒右边多少个人
        per = n - sick[sick.length - 1] - 1;
        perTotal *= INV_FAC[per];
        perTotal %= MOD;

        // 每种区间内部方案数 * 区间之间的排列数
        res = qPow(2, ansPow, MOD) * perTotal % MOD;

        return (int)(res);
    }

    // 组合数模板
    private static final int MOD = (int)1e9+7;
    private static final int MX = 100_000;
    // 阶乘
    private static final long[] FAC = new long[MX];
    // 阶乘的逆元
    private static final long[] INV_FAC = new long[MX];

    static {
        FAC[0] = 1;
        for (int i = 1; i < MX; i++) {
            FAC[i] = FAC[i - 1] * i % MOD;
        }

        INV_FAC[MX - 1] = qPow(FAC[MX - 1], MOD - 2, MOD);
        for (int i = MX - 1; i > 0; i--) {
            INV_FAC[i - 1] = INV_FAC[i] * i % MOD;
        }
    }

    private static long qPow(long value, long pow, long mod) {
        long res = 1;
        while (pow > 0) {
            if ((pow &amp; 1) == 1) {
                res *= value;
                res %= mod;
            }

            value *= value;
            value %= mod;
            pow >>= 1;
        }
        return res;
    }