湖南省新邵县建设局网站,韩国电视剧,佛山搜索引擎优化,网站建设通知Leetcode 2954. Count the Number of Infection Sequences 1. 解题思路2. 代码实现 题目链接#xff1a;2954. Count the Number of Infection Sequences
1. 解题思路
这道题其实思路上还是挺简单的#xff0c;就是一个数学问题#xff0c;还是那种不太难的数学问题。
显…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-m1 n−m1段其中头尾两段的传播方向只能是单向的而剩余的 m − 1 m-1 m−1段则每一段都有 2 x i − 1 2^{x_i-1} 2xi−1种传播序列 x i 0 x_i0 xi0。
此时总的传播序列数目就为 Π i 1 m − 1 2 x i − 1 \mathop{\Pi}\limits_{i1}^{m-1}2^{x_i-1} i1Πm−12xi−1
然后各段序列之间是可以有不同的组合方式的而这个就是一个排列组合问题对应的序列可能性就是 Π i 0 m C ∑ j ≤ i x i x i \mathop{\Pi}\limits_{i0}^{m} \mathop{C}_{\sum\limits_{j \leq i} x_i}^{x_i} i0ΠmCj≤i∑xixi
将两式相乘即可得到我们总的可能的序列数目。
但是实际在做的时候一直遇到超时问题因为 C n m n ! m ! ( n − m ) ! C_n^m \frac{n!}{m!(n-m)!} Cnmm!(n−m)!n!这个计算是很繁琐的而且还有同余的问题就一直处理不好。
最后是看了一下其他大佬的解答才豁然开朗发现算法还是这么个算法但是优化点在于说提前先算好 n ! n! n!并记录下来然后对于 C n m C_n^m Cnm的计算就不用每次都反复求一遍了。
唉感觉自己还是傻了……
2. 代码实现
给出python代码实现如下
MOD 10**9 7lru_cache(None)
def get_facts():facts [1 for _ in range(10**51)]for i in range(2, 10**51):facts[i] i * facts[i-1] % MODreturn factsFACTS get_facts()
def C(n, m):return FACTS[n] * pow(FACTS[m], -1, modMOD) * pow(FACTS[n-m], -1, modMOD) % 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(ab, a)s a bm len(sick)for i in range(m-1):k sick[i1] - sick[i]-1if k 0:s kans ans * pow(2, k-1, modMOD) * C(s, k) % MODreturn ans提交代码评测得到耗时404ms占用内存20.6MB。
