2954. Count the Number of Infection Sequences Hard

1/**
2 * [2954] Count the Number of Infection Sequences
3 *
4 * 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.
5 * At each step, one uninfected person adjacent to an infected person gets infected. This process continues until everyone is infected.
6 * An infection sequence is the order in which uninfected people become infected, excluding those initially infected.
7 * Return the number of different infection sequences possible, modulo 10^9+7.
8 *  
9 * <strong class="example">Example 1:
10 * <div class="example-block">
11 * Input: <span class="example-io">n = 5, sick = [0,4]</span>
12 * Output: <span class="example-io">4</span>
13 * Explanation:
14 * There is a total of 6 different sequences overall.
15 * 
16 * 	Valid infection sequences are [1,2,3], [1,3,2], [3,2,1] and [3,1,2].
17 * 	[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.
18 * </div>
19 * <strong class="example">Example 2:
20 * <div class="example-block">
21 * Input: <span class="example-io">n = 4, sick = [1]</span>
22 * Output: <span class="example-io">3</span>
23 * Explanation:
24 * There is a total of 6 different sequences overall.
25 * 
26 * 	Valid infection sequences are [0,2,3], [2,0,3] and [2,3,0].
27 * 	[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.
28 * </div>
29 *  
30 * Constraints:
31 * 
32 * 	2 <= n <= 10^5
33 * 	1 <= sick.length <= n - 1
34 * 	0 <= sick[i] <= n - 1
35 * 	sick is sorted in increasing order.
36 * 
37 */
38pub struct Solution {}
39
40// problem: https://leetcode.com/problems/count-the-number-of-infection-sequences/
41// discuss: https://leetcode.com/problems/count-the-number-of-infection-sequences/discuss/?currentPage=1&orderBy=most_votes&query=
42
43// submission codes start here
44
45impl Solution {
46    pub fn number_of_sequence(n: i32, sick: Vec<i32>) -> i32 {
47        0
48    }
49}
50
51// submission codes end
52
53#[cfg(test)]
54mod tests {
55    use super::*;
56
57    #[test]
58    fn test_2954() {
59    }
60}
61