给你一个整数 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
按升序排列。0
and non-infected as 1
, then divide the array into segments with the same value.[i, j]
and indices (i - 1)
and (j + 1)
, if they exist, are already infected. Then if i == 0
or j == n - 1
, each second there is only one kid that can be infected (which is at the other endpoint).i > 0
and j < n - 1
, we have two choices per second since the children at the two endpoints can both be the infect candidates. So there are 2j - i
orders to infect all children in the segment.S! / (len[1]! * len[2]! * ... * len[m]! * lenstart! * lenend!) * 2k
where len[1], len[2], ..., len[m]
are the lengths of each segment of non-infected children that have an infected child at both endpoints, lenstart
and lenend
denote the number of non-infected children with infected child at one endpoint, S
is the total length of all segments of non-infected children, and k = (len[1] - 1) + (len[2] - 1) + ... + (len[m] - 1)
.