以下是 LeetCode 3426. 所有安放棋子方案的曼哈顿距离 的 Java 实现。---解题思路这道题的核心是 组合数学 贡献法时间复杂度 O(log MOD)空间复杂度 O(1)。关键观察1. 贡献法任选两个格子 A 和 B设它们之间的曼哈顿距离为 d。在所有 C(m*n, k) 种方案中包含这两个格子的方案数为 C(m*n-2, k-2)。因此这对格子对答案的总贡献 d * C(m*n-2, k-2)。2. 由于所有点对的重数相同我们可以先计算 k2 时的总距离再乘以 C(m*n-2, k-2) 即可。3. 计算 k2 时的总距离将曼哈顿距离拆分为行差和列差- 行差对于距离 d1 ≤ d ≤ m-1有 (m-d) 对行可以选择。对于每对行两个棋子各有 n 种列的选择所以贡献为 d * (m-d) * n²。总和 n² * Σ(d*(m-d)) n² * (m³ - m) / 6- 列差对称总和 m² * (n³ - n) / 64. 组合数计算使用费马小定理计算逆元时间复杂度 O(k) 或 O(log MOD)。---Java 完整代码javaclass Solution {private static final int MOD 1_000_000_007;public int distanceSum(int m, int n, int k) {// 计算行方向的贡献: n^2 * (m^3 - m) / 6long rowContrib (long) n * n % MOD;long mCubeMinusM ((long) m * m % MOD * m % MOD - m MOD) % MOD;rowContrib rowContrib * mCubeMinusM % MOD * modInverse(6, MOD) % MOD;// 计算列方向的贡献: m^2 * (n^3 - n) / 6long colContrib (long) m * m % MOD;long nCubeMinusN ((long) n * n % MOD * n % MOD - n MOD) % MOD;colContrib colContrib * nCubeMinusN % MOD * modInverse(6, MOD) % MOD;// k2 时的总距离long totalDistK2 (rowContrib colContrib) % MOD;// 乘以 C(m*n-2, k-2)long comb nCk(m * n - 2, k - 2);return (int) (totalDistK2 * comb % MOD);}// 计算组合数 C(n, k) mod MODprivate long nCk(int n, int k) {long res 1;for (int i 1; i k; i) {res res * (n - i 1) % MOD;res res * modInverse(i, MOD) % MOD;}return res;}// 快速幂计算 x^(-1) mod MOD费马小定理private long modInverse(long x, int mod) {return modPow(x, mod - 2, mod);}// 快速幂计算 x^n mod modprivate long modPow(long x, long n, int mod) {long res 1;x x % mod;while (n 0) {if ((n 1) 1) {res res * x % mod;}x x * x % mod;n 1;}return res;}}---测试验证输入 输出 说明m2, n2, k2 8 6 种方案4 种距离为 12 种距离为 2总和 4×1 2×2 8m1, n4, k3 20 4 种方案首尾距离为 4中间距离为 6总和 4 6 6 4 20m1, n4, k4 10 1 种方案距离 112 3不对应为 123 6需要验证m5, n1, k5 20 1 种方案距离 1234 10需要验证 注后两个示例的具体数值以 LeetCode 官方验证为准核心算法逻辑组合数学 贡献法是正确的。下载完整代码[leetcode_3426.java](sandbox:///mnt/agents/output/leetcode_3426.java)