Leetcode 2954. Count the Number of Infection Sequences

本文主要是介绍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$ 个生病的人将所有的 $n$ 个人分成了 $n - m + 1$ 段，其中头尾两段的传播方向只能是单向的，而剩余的 $m - 1$ 段则每一段都有 $2^{x_i-1}$ 种传播序列（ $x_i>0$ ）。

此时，总的传播序列数目就为：

$\mathop{\Pi}\limits_{i=1}^{m-1}2^{x_i-1}$

然后，各段序列之间是可以有不同的组合方式的，而这个就是一个排列组合问题，对应的序列可能性就是：

$\mathop{\Pi}\limits_{i=0}^{m} \mathop{C}_{\sum\limits_{j \leq i} x_i}^{x_i}$

将两式相乘即可得到我们总的可能的序列数目。

但是实际在做的时候一直遇到超时问题，因为 $C_n^m = \frac{n!}{m!(n-m)!}$ 这个计算是很繁琐的，而且还有同余的问题，就一直处理不好。

最后是看了一下其他大佬的解答才豁然开朗，发现算法还是这么个算法，但是优化点在于说提前先算好 $n!$ 并记录下来，然后对于 $C_n^m$ 的计算就不用每次都反复求一遍了。

唉，感觉自己还是傻了……

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] % MODreturn factsFACTS = get_facts()
def C(n, m):return FACTS[n] * pow(FACTS[m], -1, mod=MOD) * pow(FACTS[n-m], -1, mod=MOD) % MODclass Solution:def numberOfSequence(self, n: int, sick: List[int]) -> int:if len(sick) == n:return 0a, b = sick[0]-0, n-1-sick[-1]ans = 1 * C(a+b, a)s = a + bm = len(sick)for i in range(m-1):k = sick[i+1] - sick[i]-1if k > 0:s += kans = ans * pow(2, k-1, mod=MOD) * C(s, k) % MODreturn ans