Hard

题目描述

给你三个整数 m、n 和 k。

有一个大小为 m × n 的矩形网格，包含 k 个相同的棋子。返回所有有效排列中每对棋子之间曼哈顿距离的总和。

有效排列是指将所有 k 个棋子放置在网格上，每个格子最多放一个棋子。

由于答案可能很大，请返回对 10^9 + 7 取模的结果。

两个格子 (xi, yi) 和 (xj, yj) 之间的曼哈顿距离是 |xi - xj| + |yi - yj|。

示例 1：

输入：m = 2, n = 2, k = 2

输出：8

解释：

棋盘上棋子的有效排列有：

  • 在前 4 种排列中，两个棋子之间的曼哈顿距离是 1。
  • 在最后 2 种排列中，两个棋子之间的曼哈顿距离是 2。

因此，所有有效排列的曼哈顿距离总和是 1 + 1 + 1 + 1 + 2 + 2 = 8。

示例 2：

输入：m = 1, n = 4, k = 3

输出：20

解释：

棋盘上棋子的有效排列有：

  • 第一种和最后一种排列的曼哈顿距离总和是 1 + 1 + 2 = 4。
  • 中间两种排列的曼哈顿距离总和是 1 + 2 + 3 = 6。

所有排列中所有棋子对之间的曼哈顿距离总和是 4 + 6 + 6 + 4 = 20。

约束条件：

  • 1 <= m, n <= 10^5
  • 2 <= m * n <= 10^5
  • 2 <= k <= m * n

解题思路

这是一道需要数学思维的组合数学题目。关键洞察是：我们不需要枚举所有排列，而是考虑每一对位置在所有排列中被选中的次数。

核心思路：

  1. 固定两个位置的思考：对于网格中任意两个位置 (i₁, j₁) 和 (i₂, j₂)，我们需要计算这两个位置同时被棋子占据的排列数量。

  2. 组合数计算：如果我们固定了两个特定位置放置棋子，那么剩下的 k-2 个棋子需要从剩余的 m×n-2 个位置中选择，方案数为 C(m×n-2, k-2)。

  3. 距离贡献分离：曼哈顿距离可以分解为 x 坐标差的绝对值和 y 坐标差的绝对值之和。我们可以分别计算这两部分的贡献。

  4. 优化计算：

    • 对于 x 坐标：计算所有行对 (i₁, i₂) 的 |i₁ - i₂| × n² × C(m×n-2, k-2) 的总和
    • 对于 y 坐标：计算所有列对 (j₁, j₂) 的 |j₁ - j₂| × m² × C(m×n-2, k-2) 的总和

  5. 数学公式推导：

    • x 方向贡献：∑∑|i-j| × n² = n² × m(m-1)(m+1)/6
    • y 方向贡献：∑∑|i-j| × m² = m² × n(n-1)(n+1)/6

最终答案 = C(m×n-2, k-2) × [n² × m(m-1)(m+1)/6 + m² × n(n-1)(n+1)/6]

代码实现

class Solution {
public:
    static const int MOD = 1000000007;
    
    long long modPow(long long base, long long exp, long long mod) {
        long long result = 1;
        while (exp > 0) {
            if (exp % 2 == 1) {
                result = (result * base) % mod;
            }
            base = (base * base) % mod;
            exp /= 2;
        }
        return result;
    }
    
    long long modInverse(long long a, long long mod) {
        return modPow(a, mod - 2, mod);
    }
    
    long long combination(int n, int r) {
        if (r > n || r < 0) return 0;
        if (r == 0 || r == n) return 1;
        
        long long num = 1, den = 1;
        for (int i = 0; i < r; i++) {
            num = (num * (n - i)) % MOD;
            den = (den * (i + 1)) % MOD;
        }
        return (num * modInverse(den, MOD)) % MOD;
    }
    
    int distanceSum(int m, int n, int k) {
        long long total = (long long)m * n;
        long long comb = combination(total - 2, k - 2);
        
        // x direction contribution: sum of |i1 - i2| over all pairs
        long long xContrib = ((long long)m * (m - 1) * (m + 1) / 6) % MOD;
        xContrib = (xContrib * n % MOD * n) % MOD;
        
        // y direction contribution: sum of |j1 - j2| over all pairs  
        long long yContrib = ((long long)n * (n - 1) * (n + 1) / 6) % MOD;
        yContrib = (yContrib * m % MOD * m) % MOD;
        
        long long result = (xContrib + yContrib) % MOD;
        result = (result * comb) % MOD;
        
        return (int)result;
    }
};

class Solution:
    def distanceSum(self, m: int, n: int, k: int) -> int:
        MOD = 1000000007
        
        def mod_inverse(a, mod):
            return pow(a, mod - 2, mod)
        
        def combination(n, r):
            if r > n or r < 0:
                return 0
            if r == 0 or r == n:
                return 1
            
            num = 1
            den = 1
            for i in range(r):
                num = (num * (n - i)) % MOD
                den = (den * (i + 1)) % MOD
            
            return (num * mod_inverse(den, MOD)) % MOD
        
        total = m * n
        comb = combination(total - 2, k - 2)
        
        # x direction contribution
        x_contrib = (m * (m - 1) * (m + 1) // 6) % MOD
        x_contrib = (x_contrib * n * n) % MOD
        
        # y direction contribution
        y_contrib = (n * (n - 1) * (n + 1) // 6) % MOD
        y_contrib = (y_contrib * m * m) % MOD
        
        result = (x_contrib + y_contrib) % MOD
        result = (result * comb) % MOD
        
        return result

public class Solution {
    private const int MOD = 1000000007;
    
    private long ModPow(long baseNum, long exp, long mod) {
        long result = 1;
        while (exp > 0) {
            if (exp % 2 == 1) {
                result = (result * baseNum) % mod;
            }
            baseNum = (baseNum * baseNum) % mod;
            exp /= 2;
        }
        return result;
    }
    
    private long ModInverse(long a, long mod) {
        return ModPow(a, mod - 2, mod);
    }
    
    private long Combination(int n, int r) {
        if (r > n || r < 0) return 0;
        if (r == 0 || r == n) return 1;
        
        long num = 1, den = 1;
        for (int i = 0; i < r; i++) {
            num = (num * (n - i)) % MOD;
            den = (den * (i + 1)) % MOD;
        }
        return (num * ModInverse(den, MOD)) % MOD;
    }
    
    public int DistanceSum(int m, int n, int k) {
        long total = (long)m * n;
        long comb = Combination((int)total - 2, k - 2);
        
        // x direction contribution
        long xContrib = ((long)m * (m - 1) * (m + 1) / 6) % MOD;
        xContrib = (xContrib * n % MOD * n) % MOD;
        
        // y direction contribution
        long yContrib = ((long)n * (n - 1) * (n + 1) / 6) % MOD;
        yContrib = (yContrib * m % MOD * m) % MOD;
        
        long result = (xContrib + yContrib) % MOD;
        result = (result * comb) % MOD;
        
        return (int)result;
    }
}

var distanceSum = function(m, n, k) {
    const MOD = 1000000007;
    
    // Total number of ways to choose k positions from m*n positions
    const totalArrangements = comb(m * n, k, MOD);
    
    // For each pair of positions, count how many arrangements contain both
    const arrangementsPerPair = comb(m * n - 2, k - 2, MOD);
    
    let totalDistance = 0;
    
    // Sum Manhattan distances for all pairs of positions
    for (let i1 = 0; i1 < m; i1++) {
        for (let j1 = 0; j1 < n; j1++) {
            for (let i2 = 0; i2 < m; i2++) {
                for (let j2 = 0; j2 < n; j2++) {
                    if (i1 === i2 && j1 === j2) continue;
                    
                    const manhattanDist = Math.abs(i1 - i2) + Math.abs(j1 - j2);
                    totalDistance = (totalDistance + (manhattanDist * arrangementsPerPair) % MOD) % MOD;
                }
            }
        }
    }
    
    return totalDistance;
};

function comb(n, k, mod) {
    if (k > n || k < 0) return 0;
    if (k === 0 || k === n) return 1;
    
    // Calculate n! / (k! * (n-k)!)
    let num = 1, den = 1;
    
    for (let i = 0; i < k; i++) {
        num = (num * ((n - i) % mod)) % mod;
        den = (den * (i + 1)) % mod;
    }
    
    return (num * modInverse(den, mod)) % mod;
}

function modInverse(a, mod) {
    return modPow(a, mod - 2, mod);
}

function modPow(base, exp, mod) {
    let result = 1;
    base %= mod;
    
    while (exp > 0) {
        if (exp & 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exp >>= 1;
    }
    
    return result;
}
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

维度复杂度
时间复杂度O(k)
空间复杂度O(1)

说明：

  • 时间复杂度：主要消耗在计算组合数 C(m×n-2, k-2)，需要 O(k) 时间
  • 空间复杂度：只使用了常数级别的额外空间