统计感冒序列的数目

难度: Hard

给你一个整数 n 和一个下标从 0 开始的整数数组 sick ，数组按升序排序。

有 n 位小朋友站成一排，按顺序编号为 0 到 n - 1 。数组 sick 包含一开始得了感冒的小朋友的位置。如果位置为 i 的小朋友得了感冒，他会传染给下标为 i - 1 或者 i + 1 的小朋友，前提是被传染的小朋友存在且还没有得感冒。每一秒中， 至多一位 还没感冒的小朋友会被传染。

经过有限的秒数后，队列中所有小朋友都会感冒。感冒序列 指的是所有一开始没有感冒的小朋友最后得感冒的顺序序列。请你返回所有感冒序列的数目。

由于答案可能很大，请你将答案对 10⁹ + 7 取余后返回。

注意，感冒序列不包含一开始就得了感冒的小朋友的下标。

示例 1：

输入：n = 5, sick = [0,4]
输出：4
解释：一开始，下标为 1 ，2 和 3 的小朋友没有感冒。总共有 4 个可能的感冒序列：
- 一开始，下标为 1 和 3 的小朋友可以被传染，因为他们分别挨着有感冒的小朋友 0 和 4 ，令下标为 1 的小朋友先被传染。
然后，下标为 2 的小朋友挨着感冒的小朋友 1 ，下标为 3 的小朋友挨着感冒的小朋友 4 ，两位小朋友都可以被传染，令下标为 2 的小朋友被传染。
最后，下标为 3 的小朋友被传染，因为他挨着感冒的小朋友 2 和 4 ，感冒序列为 [1,2,3] 。
- 一开始，下标为 1 和 3 的小朋友可以被传染，因为他们分别挨着感冒的小朋友 0 和 4 ，令下标为 1 的小朋友先被传染。
然后，下标为 2 的小朋友挨着感冒的小朋友 1 ，下标为 3 的小朋友挨着感冒的小朋友 4 ，两位小朋友都可以被传染，令下标为 3 的小朋友被传染。
最后，下标为 2 的小朋友被传染，因为他挨着感冒的小朋友 1 和 3 ，感冒序列为  [1,3,2] 。
- 感冒序列 [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, sick = [1]
输出：3
解释：一开始，下标为 0 ，2 和 3 的小朋友没有感冒。总共有 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] 。

提示：

2 <= n <= 10⁵
1 <= sick.length <= n - 1
0 <= sick[i] <= n - 1
sick 按升序排列。

Submission

运行时间: 64 ms

内存: 20.6 MB

mod = 10 ** 9 + 7

factorial = [1] * (10 ** 5 + 1)
for i in range(1, 10 ** 5 + 1):
    factorial[i] = i * factorial[i-1] % mod

class Solution:
    def numberOfSequence(self, n: int, sick: List[int]) -> int:
        sick = sick
        
        # 所有 2 的次幂的次数和
        cnt_pow2 = 0
        
        # v 分别表示分母，分子为 factorial[n - len(sick)]
        v = 1
        
        for i in range(len(sick) - 1):
            tmp = sick[i+1] - sick[i] - 1
            if tmp:
                v *= factorial[tmp]
                v %= mod
                cnt_pow2 += tmp - 1
        
        v *= factorial[sick[0]] * factorial[n - 1 - sick[-1]] % mod
        v %= mod
        return pow(2, cnt_pow2, mod) * factorial[n - len(sick)] % mod * pow(v, mod - 2, mod) % mod

Explain

题解的主要思路是将问题转化为排列组合问题。给定n位小朋友中，一些已经感冒的小朋友分割出不同的段，每个段内部的小朋友是独立的，并可以在各自的段内自由感染。首先，计算整体可能的感冒序列数目为感冒小朋友之间未感冒小朋友的全排列，乘以边界未感冒小朋友的排列方式。为了计算排列方式，预先计算出阶乘数和使用费马小定理进行模逆计算，因为直接的除法运算在模运算中不适用。另外，使用快速幂计算2的幂，因为每一对小朋友之间的间隔都存在两种传染可能性。

时间复杂度: O(n)

空间复杂度: O(n)

mod = 10 ** 9 + 7

# 预计算阶乘数并进行模运算以适应大数情况
factorial = [1] * (10 ** 5 + 1)
for i in range(1, 10 ** 5 + 1):
    factorial[i] = i * factorial[i-1] % mod

class Solution:
    def numberOfSequence(self, n: int, sick: List[int]) -> int:
        # 使用sick数组记录已感冒小朋友的索引
        sick = sick

        # 计算所有需要考虑的2的幂次总和
        cnt_pow2 = 0

        # v用于计算最终结果的分母部分，初始化为1
        v = 1

        # 遍历sick数组，计算每一段未感冒小朋友的数量
        for i in range(len(sick) - 1):
            tmp = sick[i+1] - sick[i] - 1
            if tmp:
                v *= factorial[tmp]
                v %= mod
                cnt_pow2 += tmp - 1

        # 加入边界小朋友的阶乘计算
        v *= factorial[sick[0]] * factorial[n - 1 - sick[-1]] % mod
        v %= mod
        # 计算最终可能的感冒序列数目
        return pow(2, cnt_pow2, mod) * factorial[n - len(sick)] % mod * pow(v, mod - 2, mod) % mod

Explore

在`sick`数组中如果存在相邻两个元素相等的情况，即两个已感冒的小朋友紧挨着，这表示在他们之间没有未感冒的小朋友。在这种情况下，tmp（两个sick小朋友之间的未感冒小朋友数量）为0，因此在计算各部分的阶乘时，tmp对应的阶乘是factorial[0]，即1。此外，因为没有未感冒的小朋友，所以也不会有新增的传染方式（2的幂次项不增加）。因此，这种情况不会对病毒传播的序列数目产生影响，可以简单地将这两个相等的sick索引视为一个，计算时跳过其中一个即可。

在给定的模型中，虽然每秒中至多一位未感冒的小朋友会被传染，但是整体的传染序列数目是由未感冒小朋友的全排列决定的。因为每个未感冒的小朋友最终都将被感染，其感染的具体顺序不影响最终的序列数目。我们计算的是所有可能的排列方式，这包括了所有可能的感染顺序。因此，虽然每秒的感染事件是序列化的，整体来看，感染顺序的不同配置不会影响最终可能的序列总数。这里的关键在于理解，尽管过程是序列化，所有可能的排列组合都被考虑在内。

费马小定理指出，如果p是一个质数，那么对于任何整数a，只要a不是p的倍数，就有a的(p-1)次方与1同余，即a^(p-1) ≡ 1 (mod p)。从这一定理可以推导出，a的(p-2)次方就是a模p的乘法逆元，即a^(p-2) ≡ a^(-1) (mod p)。在题解中，因为模数mod是一个质数（10^9+7），我们需要对某些运算结果取逆元以进行除法运算，这时就可以利用费马小定理。具体地，如果要计算v的逆元，我们计算v^(mod-2) % mod。这在Python中可以通过pow函数实现，即pow(v, mod-2, mod)，这样就能得到v在模mod下的逆，以进行之后的除法运算。