Question

2954. 统计感冒序列的数目

English Version

题目描述

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

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

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

由于答案可能很大，请你将答案对 109 + 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 <= 105
• 1 <= sick.length <= n - 1
• 0 <= sick[i] <= n - 1
• sick 按升序排列。

解法

方法一：组合数学 + 乘法逆元 + 快速幂

根据题目描述，感冒的小朋友把还没有感冒的小朋友划分成了若干个连续段。我们可以用一个数组 $nums$ 记录每一段不感冒的小朋友的认识，不感冒人数一共有 $s = \sum_{i=0}^{k} nums[k]$ 人。我们可以发现，感冒序列的数目就是 $s$ 个不同元素的全排列数，即 $s!$。

假设每一段不感冒小朋友只有一种传播方案，那么一共有 $\frac{s!}{\prod_{i=0}^{k} nums[k]!}$ 种感冒序列。

接下来，我们再考虑每一段不感冒小朋友的传播方案。假设一段不感冒小朋友有 $x$ 个人，那么他们的传播方案有 $2^{x-1}$ 种，因为每一次可以从一段的左右两端选择其中一端传播，即：两种选择，一共有 $x-1$ 次传播。不过，如果是第一段或者最后一段，那么只有一种选择。

综上所述，总的感冒序列数目为：

$$ \frac{s!}{\prod_{i=0}^{k} nums[k]!} \prod_{i=1}^{k-1} 2^{nums[i]-1} $$

最后，我们需要考虑到答案可能很大，需要对 $10^9 + 7$ 取模。因此，我们需要预处理阶乘和乘法逆元。

时间复杂度 $O(m)$，其中 $m$ 是数组 $sick$ 的长度。忽略预处理数组的空间消耗，空间复杂度 $O(m)$。

mod = 10**9 + 7
mx = 10**5
fac = [1] * (mx + 1)
for i in range(2, mx + 1):
  fac[i] = fac[i - 1] * i % mod


class Solution:
  def numberOfSequence(self, n: int, sick: List[int]) -> int:
    nums = [b - a - 1 for a, b in pairwise([-1] + sick + [n])]
    ans = 1
    s = sum(nums)
    ans = fac[s]
    for x in nums:
      if x:
        ans = ans * pow(fac[x], mod - 2, mod) % mod
    for x in nums[1:-1]:
      if x > 1:
        ans = ans * pow(2, x - 1, mod) % mod
    return ans

class Solution {
  private static final int MOD = (int) (1e9 + 7);
  private static final int MX = 100000;
  private static final int[] FAC = new int[MX + 1];

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

  public int numberOfSequence(int n, int[] sick) {
    int m = sick.length;
    int[] nums = new int[m + 1];
    nums[0] = sick[0];
    nums[m] = n - sick[m - 1] - 1;
    for (int i = 1; i < m; i++) {
      nums[i] = sick[i] - sick[i - 1] - 1;
    }
    int s = 0;
    for (int x : nums) {
      s += x;
    }
    int ans = FAC[s];
    for (int x : nums) {
      if (x > 0) {
        ans = (int) ((long) ans * qpow(FAC[x], MOD - 2) % MOD);
      }
    }
    for (int i = 1; i < nums.length - 1; ++i) {
      if (nums[i] > 1) {
        ans = (int) ((long) ans * qpow(2, nums[i] - 1) % MOD);
      }
    }
    return ans;
  }

  private int qpow(long a, long n) {
    long ans = 1;
    for (; n > 0; n >>= 1) {
      if ((n & 1) == 1) {
        ans = ans * a % MOD;
      }
      a = a * a % MOD;
    }
    return (int) ans;
  }
}

const int MX = 1e5;
const int MOD = 1e9 + 7;
int fac[MX + 1];

auto init = [] {
  fac[0] = 1;
  for (int i = 1; i <= MX; ++i) {
    fac[i] = 1LL * fac[i - 1] * i % MOD;
  }
  return 0;
}();

int qpow(long long a, long long n) {
  long long ans = 1;
  for (; n > 0; n >>= 1) {
    if (n & 1) {
      ans = (ans * a) % MOD;
    }
    a = (a * a) % MOD;
  }
  return ans;
}

class Solution {
public:
  int numberOfSequence(int n, vector<int>& sick) {
    int m = sick.size();
    vector<int> nums(m + 1);

    nums[0] = sick[0];
    nums[m] = n - sick[m - 1] - 1;
    for (int i = 1; i < m; i++) {
      nums[i] = sick[i] - sick[i - 1] - 1;
    }

    int s = accumulate(nums.begin(), nums.end(), 0);
    long long ans = fac[s];
    for (int x : nums) {
      if (x > 0) {
        ans = ans * qpow(fac[x], MOD - 2) % MOD;
      }
    }
    for (int i = 1; i < nums.size() - 1; ++i) {
      if (nums[i] > 1) {
        ans = ans * qpow(2, nums[i] - 1) % MOD;
      }
    }
    return ans;
  }
};

const MX = 1e5
const MOD = 1e9 + 7

var fac [MX + 1]int

func init() {
  fac[0] = 1
  for i := 1; i <= MX; i++ {
    fac[i] = fac[i-1] * i % MOD
  }
}

func qpow(a, n int) int {
  ans := 1
  for n > 0 {
    if n&1 == 1 {
      ans = (ans * a) % MOD
    }
    a = (a * a) % MOD
    n >>= 1
  }
  return ans
}

func numberOfSequence(n int, sick []int) int {
  m := len(sick)
  nums := make([]int, m+1)

  nums[0] = sick[0]
  nums[m] = n - sick[m-1] - 1
  for i := 1; i < m; i++ {
    nums[i] = sick[i] - sick[i-1] - 1
  }

  s := 0
  for _, x := range nums {
    s += x
  }
  ans := fac[s]
  for _, x := range nums {
    if x > 0 {
      ans = ans * qpow(fac[x], MOD-2) % MOD
    }
  }
  for i := 1; i < len(nums)-1; i++ {
    if nums[i] > 1 {
      ans = ans * qpow(2, nums[i]-1) % MOD
    }
  }
  return ans
}

const MX = 1e5;
const MOD: bigint = BigInt(1e9 + 7);
const fac: bigint[] = Array(MX + 1);

const init = (() => {
  fac[0] = 1n;
  for (let i = 1; i <= MX; ++i) {
    fac[i] = (fac[i - 1] * BigInt(i)) % MOD;
  }
  return 0;
})();

function qpow(a: bigint, n: number): bigint {
  let ans = 1n;
  for (; n > 0; n >>= 1) {
    if (n & 1) {
      ans = (ans * a) % MOD;
    }
    a = (a * a) % MOD;
  }
  return ans;
}

function numberOfSequence(n: number, sick: number[]): number {
  const m = sick.length;
  const nums: number[] = Array(m + 1);
  nums[0] = sick[0];
  nums[m] = n - sick[m - 1] - 1;
  for (let i = 1; i < m; i++) {
    nums[i] = sick[i] - sick[i - 1] - 1;
  }

  const s = nums.reduce((acc, x) => acc + x, 0);
  let ans = fac[s];
  for (let x of nums) {
    if (x > 0) {
      ans = (ans * qpow(fac[x], Number(MOD) - 2)) % MOD;
    }
  }
  for (let i = 1; i < nums.length - 1; ++i) {
    if (nums[i] > 1) {
      ans = (ans * qpow(2n, nums[i] - 1)) % MOD;
    }
  }
  return Number(ans);
}