- Leetcode 3426. Manhattan Distances of All Arrangements of Pieces
- 1. 解题思路
- 2. 代码实现
- 题目链接:3426. Manhattan Distances of All Arrangements of Pieces
1. 解题思路
这道题很惭愧,一开始没有搞定,后来看了答案想了想,发现就是一个单纯的数学题,而且是不太难的那种,唉,就很惭愧。
首先,考察每一个pair会被选到的次数,这个事实上就是 C n m − 2 k − 2 C_{nm-2}^{k-2} Cnm−2k−2,即事先将目标的两个位置占上,剩下的 k − 2 k-2 k−2个点能在图上摆放的所有情况就是其可以被选中的次数。且任意两个点组成的pair这个重复次数都是完全相同的。
然后,我们只需要考虑这个 n × m n\times m n×m的矩阵当中所有位置对的曼哈顿距离之和即可。
然后,考虑到曼哈顿距离的定义,事实上我们又可以将横向和纵向分开考虑,我们只考虑任意两个点的横向距离差,显然这个值就是:
d = m 2 × ∑ i = 0 n − 2 ∑ j = i + 1 n − 1 ( j − i ) = m 2 × ∑ i = 0 n − 2 ( n − i ) ( n − i − 1 ) 2 d = m^2 \times \sum\limits_{i=0}^{n-2}\sum\limits_{j=i+1}^{n-1} (j-i) = m^2 \times \sum\limits_{i=0}^{n-2}\frac{(n-i)(n-i-1)}{2} d=m2×i=0∑n−2j=i+1∑n−1(j−i)=m2×i=0∑n−22(n−i)(n−i−1)
同理,纵向距离差之和即为:
d = n 2 × ∑ i = 0 m − 2 ( m − i ) ( m − i − 1 ) 2 d = n^2 \times \sum\limits_{i=0}^{m-2}\frac{(m-i)(m-i-1)}{2} d=n2×i=0∑m−22(m−i)(m−i−1)
因此,总的答案就是:
D = C n m − 2 k − 2 ⋅ ( m 2 × ∑ i = 0 n − 2 ( n − i ) ( n − i − 1 ) 2 + n 2 × ∑ i = 0 m − 2 ( m − i ) ( m − i − 1 ) 2 ) D = C_{nm-2}^{k-2} \cdot (m^2 \times \sum\limits_{i=0}^{n-2}\frac{(n-i)(n-i-1)}{2} + n^2 \times \sum\limits_{i=0}^{m-2}\frac{(m-i)(m-i-1)}{2}) D=Cnm−2k−2⋅(m2×i=0∑n−22(n−i)(n−i−1)+n2×i=0∑m−22(m−i)(m−i−1))
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[n-m] * Revs[m]) % MOD if n >= m else 0class Solution:def distanceSum(self, m: int, n: int, k: int) -> int:vertical = 0for i in range(n-1):vertical += (n-i) * (n-1-i) // 2vertical = (vertical * m * m) % MODhorizon = 0for i in range(m-1):horizon += (m-i) * (m-1-i) // 2horizon = (horizon * n * n) % MODreturn C(n*m-2, k-2) * (vertical + horizon) % MOD
提交代码评测得到:耗时67ms,占用内存25.5MB。