2025-07-29：所有安放棋子方案的曼哈顿距离。用go语言，给定三个整数 m、n 和 k，表示一个 m 行 n 列的棋盘，以及需要放置的 k 个相同棋子。

任务是计算出所有可能的合法放置方案中，每个方案中所有棋子两两之间曼哈顿距离的总和，再把这些结果加起来。

所谓合法方案，指的是将这 k 个棋子都放入棋盘中，且每个格子最多放一颗棋子。

曼哈顿距离定义为两个格子坐标 (x1, y1) 和 (x2, y2) 之间距离为 |x1 - x2| + |y1 - y2|。

最终结果需要对 1000000007 取模后返回。

1 <= m, n <= 100000。

2 <= m * n <= 100000。

2 <= k <= m * n。

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

输出：8。

解释：
放置棋子的合法方案包括：

在这里插入图片描述

前 4 个方案中，两个棋子的曼哈顿距离都为 1 。

后 2 个方案中，两个棋子的曼哈顿距离都为 2 。

所以所有方案的总曼哈顿距离之和为 1 + 1 + 1 + 1 + 2 + 2 = 8 。

题目来自力扣3426。

代码和算法思路分步骤

1. 预处理阶乘及其逆元（组合数计算准备）

o 目标是方便计算组合数 C(n, k) = n! / (k! * (n-k)!)

o 因为计算组合数时需要快速求阶乘和阶乘逆元。

o 初始化数组：

• f[i] 存储 i 的阶乘 i! 取模后的结果。
• invF[i] 存储 i! 的模逆元，方便快速求组合数。

o 阶乘预处理利用循环计算从 1! 到 (mx-1)!，mx 是最大值（预设为 100000，满足题目规模）。

o 阶乘逆元利用费马小定理（快速幂求逆元）：

• 计算 (mx-1)! 的逆元。
• 利用递推 invF[i-1] = invF[i] * i % mod 计算出所有逆元。

o 这样，之后在计算组合数时能够 O(1) 取值。

2. 快速幂函数

o 计算 a^b % mod，模数为 10^9+7。

o 使用“平方乘法”快速幂算法实现，在 O(log b) 时间内计算幂。

o 主要用于计算阶乘的逆元，费马小定理的逆元求解。

3. 组合数计算函数（comb）

o 给定参数 n 和 m，计算组合数 C(n, m)。

o 利用阶乘和逆元数组快速计算：f[n] * invF[m] * invF[n-m] % mod

o 计算效率是 O(1)，非常高效。

4. 计算两两曼哈顿距离总和的核心公式（distanceSum）

o 代码里的 distanceSum 函数计算所有方案中两两曼哈顿距离的总和。

o 公式部分：
.

  return (m * n * (m*(n*n - 1) + n*(m*m - 1))) / 6 % mod * comb(m*n - 2, k - 2) % mod

o 公式拆解解释：

• 首先计算全部格子两两曼哈顿距离之和。
• m * n 是格子总数。
• (m*(n*n - 1) + n*(m*m - 1)) / 6 是棋盘中两格之间曼哈顿距离的总和经数学推导得出的公式。
• 乘以组合数 C(m*n - 2, k - 2) 表示从剩余格子中选出其他的棋子位置，保证总共 k 个棋子，且这两格都是被选中的情况数。
• 结果为所有棋子两两之间曼哈顿距离和的总和。

o 利用了组合数和数学上的组合推导，避免暴力枚举，非常高效。

5. 主函数演示（main）

o 给定简单测试用例 m=2, n=2, k=2。

o 调用 distanceSum 计算距离总和。

o 输出结果正确（题目示例中结果为8）。

总体思路总结

1. 预处理阶乘和逆元，方便快速计算组合数。

2. 使用数学推导的曼哈顿距离总和公式，不用枚举所有组合。

3. 使用组合数考虑多个棋子的不同选择方案数量。

4. 对结果取模保证数字不溢出。

5. 通过前面步骤获得最终所有合法方案曼哈顿距离和。

时间复杂度分析

o 阶乘和逆元预处理复杂度：O(mx)，mx=100000（固定最大值）

o 快速幂求逆元复杂度：O(log mod)，单次，几乎可忽略

o 计算组合数是 O(1)

o 计算曼哈顿距离总和公式是 O(1)

o 总体运行时只受限于预处理阶乘数组的线性时间

综合时间复杂度： O(mx) ≈ O(100000)，即线性复杂度

空间复杂度分析

o 需要存储两个长度为 mx 的数组：f 和 invF

o 每个数组大小为 mx（100,000 整数）

o 其他额外变量常数空间

综合空间复杂度： O(mx) = O(100000)

小结

o 利用预处理和数学组合推导，问题从暴力枚举（组合高达 C(m*n, k)）降到线性预处理加 O(1) 的计算。

o 时间复杂度线性且绝大部分为预处理，在线查询速度快。

o 空间复杂度主要用于存储阶乘和逆元数组。

o 该方案适用于 m*n 最大值约为 100,000 的情况，满足题目限制。

Go完整代码如下：

.

package main

import (
    "fmt"
)

const mod = 1_000_000_007
const mx = 100_000

var f [mx]int    // f[i] = i!
var invF [mx]int// invF[i] = i!^-1

func init() {
    f[0] = 1
    for i := 1; i < mx; i++ {
        f[i] = f[i-1] * i % mod
    }

    invF[mx-1] = pow(f[mx-1], mod-2)
    for i := mx - 1; i > 0; i-- {
        invF[i-1] = invF[i] * i % mod
    }
}

func pow(x, n int)int {
    res := 1
    for ; n > 0; n /= 2 {
        if n%2 > 0 {
            res = res * x % mod
        }
        x = x * x % mod
    }
    return res
}

func comb(n, m int)int {
    return f[n] * invF[m] % mod * invF[n-m] % mod
}

func distanceSum(m, n, k int)int {
    return (m * n * (m*(n*n-1) + n*(m*m-1))) / 6 % mod * comb(m*n-2, k-2) % mod
}

func main() {
    m := 2
    n := 2
    k := 2
    result := distanceSum(m, n, k)
    fmt.Println(result)
}

Python完整代码如下：

.

# -*-coding:utf-8-*-

MOD = 10**9 + 7
MX = 100_000

# 预处理阶乘和逆阶乘
f = [1] * MX
invF = [1] * MX

def pow_mod(x, n):
    res = 1
    while n > 0:
        if n & 1:
            res = res * x % MOD
        x = x * x % MOD
        n >>= 1
    return res

def init():
    for i in range(1, MX):
        f[i] = f[i-1] * i % MOD
    invF[MX-1] = pow_mod(f[MX-1], MOD-2)
    for i in range(MX-2, -1, -1):
        invF[i] = invF[i+1] * (i+1) % MOD

def comb(n, m):
    if m > n or m < 0:
        return0
    return f[n] * invF[m] % MOD * invF[n-m] % MOD

def distance_sum(m, n, k):
    total_cells = m * n
    # 利用整除可能导致问题，先用乘法顺序计算，再对MOD取模避免整除误差
    part1 = (m * (n * n - 1)) % MOD
    part2 = (n * (m * m - 1)) % MOD
    val = (total_cells * (part1 + part2)) % MOD
    # 除以6相当于乘以6的逆元
    inv6 = pow_mod(6, MOD - 2)
    val = val * inv6 % MOD
    val = val * comb(total_cells - 2, k - 2) % MOD
    return val

if __name__ == "__main__":
    init()
    m = 2
    n = 2
    k = 2
    print(distance_sum(m, n, k))

·

我们相信Go语言和算法为普通开发者提供了困境的“面试利器”，并致力于分享全面的编程知识。在这里，您可以找到最新的Go语言教程、算法解析、提升面试竞争力的秘籍以及行业动态。

欢迎关注“福大规模架构师每日一题”，让 Go 语言和算法助力您的职业发展

·