How do you handle segments at the ends of the line in Count the Number of Infection Sequences?

Treat end segments as normal blocks; compute the number of infection sequences from the single adjacent infected person outward, then combine with other segments.

What pattern does this problem follow?

It follows an array plus math pattern where you divide the line into contiguous uninfected segments and use combinatorics to count sequences.

Can initially infected positions be skipped in calculations?

Yes, you exclude them from infection sequences since they do not change orderings.

Is there a faster way than simulating every infection step?

Yes, by segmenting the array and using combinatorial math, you compute total sequences without simulating all permutations.

What should I watch out for with large n values?

Use modular arithmetic and precompute factorials to prevent overflow while multiplying segment results.

#2954

Hard

auto_awesome数组·数学

LeetCode 题解工作台

统计感冒序列的数目

给你一个整数 n 和一个下标从 0 开始的整数数组 sick ，数组按升序排序。有 n 位小朋友站成一排，按顺序编号为 0 到 n - 1 。数组 sick 包含一开始得了感冒的小朋友的位置。如果位置为 i 的小朋友得了感冒，他会传染给下标为 i - 1 或者 i + 1 的小朋友，前提是…

数组数学组合数学

题目描述

给你一个整数 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 按升序排列。

lightbulb

解题思路

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

根据题目描述，感冒的小朋友把还没有感冒的小朋友划分成了若干个连续段。我们可以用一个数组 $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)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

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

speed

复杂度分析

指标	值
时间	complexity depends on iterating through segments and computing combinatorial numbers, roughly O(n) with precomputed factorials. Space complexity is O(n) to store factorials and segment lengths.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check how you segment the array and ensure proper boundaries for combinatorial counting.
question_mark
Be careful with large numbers; modular arithmetic might be necessary.
question_mark
Discuss how multiplying segment results gives the final sequence count and why this works mathematically.

warning

常见陷阱

外企场景

error
Forgetting to exclude initially infected positions when counting sequences.
error
Miscounting orders within segments that have multiple infection possibilities.
error
Not handling edge segments at the ends of the line correctly.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allowing multiple infections per step instead of one at a time changes combinatorial calculations.
arrow_right_alt
Changing the line to a circular arrangement affects adjacency rules and segment counting.
arrow_right_alt
Using a tree or graph structure instead of a line introduces more complex infection propagation patterns.

help

常见问题

外企场景

继续练习

#2963 统计好分割方案的数目 #3116 单面值组合的第 K 小金额 #3128 直角三角形