Leetcode 2954. Count the Number of Infection Sequences
- Leetcode 2954. Count the Number of Infection Sequences
- 1. 解题思路
- 2. 代码实现
- 题目链接：2954. Count the Number of Infection Sequences
1. 解题思路
这道题其实思路上还是挺简单的，就是一个数学问题，还是那种不太难的数学问题。
显然， m m m个生病的人将所有的 n n n个人分成了 n − m + 1 n-m+1 n−m+1段，其中头尾两段的传播方向只能是单向的，而剩余的 m − 1 m-1 m−1段则每一段都有 2 x i − 1 2^{x_i-1} 2xi−1种传播序列（ x i > 0 x_i>0 xi>0）。
此时，总的传播序列数目就为：
Π i = 1 m − 1 2 x i − 1 \mathop{\Pi}\limits_{i=1}^{m-1}2^{x_i-1} i=1Πm−12xi−1
然后，各段序列之间是可以有不同的组合方式的，而这个就是一个排列组合问题，对应的序列可能性就是：
Π i = 0 m C ∑ j ≤ i x i x i \mathop{\Pi}\limits_{i=0}^{m} \mathop{C}_{\sum\limits_{j \leq i} x_i}^{x_i} i=0ΠmCj≤i∑xixi
将两式相乘即可得到我们总的可能的序列数目。
但是实际在做的时候一直遇到超时问题，因为 C n m = n ! m ! ( n − m ) ! C_n^m = \frac{n!}{m!(n-m)!} Cnm=m!(n−m)!n!这个计算是很繁琐的，而且还有同余的问题，就一直处理不好。
最后是看了一下其他大佬的解答才豁然开朗，发现算法还是这么个算法，但是优化点在于说提前先算好 n ! n! n!并记录下来，然后对于 C n m C_n^m Cnm的计算就不用每次都反复求一遍了。
唉，感觉自己还是傻了……
2. 代码实现
给出python代码实现如下：
MOD = 10**9 + 7
@lru_cache(None)
def get_facts():
facts = [1 for _ in range(10**5+1)]
for i in range(2, 10**5+1):
facts[i] = i * facts[i-1] % MOD
return facts
FACTS = get_facts()
def C(n, m):
return FACTS[n] * pow(FACTS[m], -1, mod=MOD) * pow(FACTS[n-m], -1, mod=MOD) % MOD
class Solution:
def numberOfSequence(self, n: int, sick: List[int]) -> int:
if len(sick) == n:
return 0
a, b = sick[0]-0, n-1-sick[-1]
ans = 1 * C(a+b, a)
s = a + b
m = len(sick)
for i in range(m-1):
k = sick[i+1] - sick[i]-1
if k > 0:
s += k
ans = ans * pow(2, k-1, mod=MOD) * C(s, k) % MOD
return ans
提交代码评测得到：耗时404ms，占用内存20.6MB。