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$）。

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

$$\underset{i=1}{\overset{m-1}{\Pi }}{2}^{x_i-1}$$

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

$$\underset{i=0}{\overset{m}{\Pi }}{C}_{\sum _{j\le 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] % 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。