2954. Count the Number of Infection Sequences

Problem Link

Description

---

You are given an integer n and an array sick sorted in increasing order, representing positions of infected people in a line of n people.

At each step, one uninfected person adjacent to an infected person gets infected. This process continues until everyone is infected.

An infection sequence is the order in which uninfected people become infected, excluding those initially infected.

Return the number of different infection sequences possible, modulo 109+7.

 

Example 1:

Input: n = 5, sick = [0,4]

Output: 4

Explanation:

There is a total of 6 different sequences overall.

• Valid infection sequences are [1,2,3], [1,3,2], [3,2,1] and [3,1,2].
• [2,3,1] and [2,1,3] are not valid infection sequences because the person at index 2 cannot be infected at the first step.

Example 2:

Input: n = 4, sick = [1]

Output: 3

Explanation:

There is a total of 6 different sequences overall.

• Valid infection sequences are [0,2,3], [2,0,3] and [2,3,0].
• [3,2,0], [3,0,2], and [0,3,2] are not valid infection sequences because the infection starts at the person at index 1, then the order of infection is 2, then 3, and hence 3 cannot be infected earlier than 2.

 

Constraints:

• 2 <= n <= 105
• 1 <= sick.length <= n - 1
• 0 <= sick[i] <= n - 1
• sick is sorted in increasing order.

Solution

---

Python3

class Solution:
    MOD = 10 ** 9 + 7
 
    @staticmethod
    @cache
    def factorial(n: int) -> int:
        if n == 0:
            return 1
        return n * Solution.factorial(n - 1) % Solution.MOD
 
    def numberOfSequence(self, n: int, sick: List[int]) -> int:
        # DD, DDD, DDDD
        # 9! / 2! / 3! / 4! * (1) * (2 * 2 * 1) * (1)
        lengths = [sick[0], n - sick[-1] - 1]
        for a, b in pairwise(sick):
            length = b - a - 1
            if length > 0:
                lengths.append(length)
 
        res = Solution.factorial(sum(lengths))
        for i, x in enumerate(lengths):
            res *= pow(Solution.factorial(x), -1, Solution.MOD)
            res %= Solution.MOD
 
            # do not multiply by 2 for beginning and end
            if i >= 2:
                res *= pow(2, x - 1, Solution.MOD)
                res %= Solution.MOD
 
        return res