Leetcode 3405. Count the Number of Arrays with K Matching Adjacent Elements
- Leetcode 3405. Count the Number of Arrays with K Matching Adjacent Elements
- 1. 解题思路
- 2. 代码实现
- 题目链接：3405. Count the Number of Arrays with K Matching Adjacent Elements
1. 解题思路
这一题虽然是一道hard的题目，但是委实是有点名不副实了，任何一个稍微学过一些高中排列组合相关内容的同学事实上应该都对这个题目比较熟悉。
这个题目的本质事实上就是构造一个长度为 n n n的数组，然后每一个元素有 m m m种选择，且有且仅有 k k k个元素与其前一个元素相同。
显然，我们先从数组当中选定 k k k个位置，令其与其前一元素相同，则其可能的选法必然就是 C n − 1 k C_{n-1}^{k} Cn−1k，即除了第一个位置之外，剩下的 n − 1 n-1 n−1个位置均可作为侯选位置。剩下的，我们就是要够长一个长度为 n − k n-k n−k的数组，使其两两元素不同，则其可能的构造方法就可以快速算出为 m ⋅ ( m − 1 ) n − k − 1 m \cdot (m-1)^{n-k-1} m⋅(m−1)n−k−1。
两者相乘即为最终的答案：
N = m ⋅ ( m − 1 ) n − k − 1 ⋅ C n − 1 k N = m \cdot (m-1)^{n-k-1} \cdot C_{n-1}^{k} N=m⋅(m−1)n−k−1⋅Cn−1k
剩下的我们只需要用python实现一下就行了……
2. 代码实现
给出python代码实现如下：
MOD = 10**9+7Factorials = [1 for _ in range(10**5+1)]
Revs = [1 for _ in range(10**5+1)]
for i in range(2, 10**5+1):Factorials[i] = (i * Factorials[i-1]) % MODRevs[i] = pow(Factorials[i], -1, mod = MOD)def C(n, m):return (Factorials[n] * Revs[m] * Revs[n-m]) % MOD if n >= m else 0class Solution:def countGoodArrays(self, n: int, m: int, k: int) -> int:return (m * pow(m-1, n-k-1, mod=MOD) * C(n-1, k)) % MOD
提交代码评测得到：耗时0ms，占用内存25.5MB。