调试中...
困难
相关标签
相关企业
提示
给你三个整数 m ，n 和 k 。
给你一个大小为 m x n 的矩形格子，它包含 k 个没有差别的棋子。请你返回所有放置棋子的 合法方案 中，每对棋子之间的曼哈顿距离之和。
一个 合法方案 指的是将所有 k 个棋子都放在格子中且一个格子里 至多 只有一个棋子。
由于答案可能很大， 请你将它对 109 + 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 <= 1052 <= m * n <= 1052 <= k <= m * n
通过次数
754
提交次数
1.4K
通过率
54.4%
相关企业
提示 1
Fix two pieces in two specific locations and find the number of boards where this can happen.
提示 2
A particular pair of positions will be counted exactly
C(m * n - 2, k - 2) times. Calculate the total distance for all pairs of positions and multiply it with C(m * n - 2, k - 2).评论 (0)
贡献者
© 2025 领扣网络（上海）有限公司
0 人在线
行 1，列 1