3426. Manhattan Distances of All Arrangements of Pieces Hard

1/**
2 * [3426] Manhattan Distances of All Arrangements of Pieces
3 *
4 * You are given three integers <font face="monospace">m</font>, <font face="monospace">n</font>, and k.
5 * There is a rectangular grid of size m &times; n containing k identical pieces. Return the sum of Manhattan distances between every pair of pieces over all valid arrangements of pieces.
6 * A valid arrangement is a placement of all k pieces on the grid with at most one piece per cell.
7 * Since the answer may be very large, return it modulo 10^9 + 7.
8 * The Manhattan Distance between two cells (xi, yi) and (xj, yj) is |xi - xj| + |yi - yj|.
9 *  
10 * <strong class="example">Example 1:
11 * <div class="example-block">
12 * Input: <span class="example-io">m = 2, n = 2, k = 2</span>
13 * Output: <span class="example-io">8</span>
14 * Explanation:
15 * The valid arrangements of pieces on the board are:
16 * <img alt="" src="https://assets.leetcode.com/uploads/2024/12/25/4040example1.drawio" /><img alt="" src="https://assets.leetcode.com/uploads/2024/12/25/untitled-diagramdrawio.png" style="width: 441px; height: 204px;" />
17 * 
18 * 	In the first 4 arrangements, the Manhattan distance between the two pieces is 1.
19 * 	In the last 2 arrangements, the Manhattan distance between the two pieces is 2.
20 * 
21 * Thus, the total Manhattan distance across all valid arrangements is 1 + 1 + 1 + 1 + 2 + 2 = 8.
22 * </div>
23 * <strong class="example">Example 2:
24 * <div class="example-block">
25 * Input: <span class="example-io">m = 1, n = 4, k = 3</span>
26 * Output: <span class="example-io">20</span>
27 * Explanation:
28 * The valid arrangements of pieces on the board are:
29 * <img alt="" src="https://assets.leetcode.com/uploads/2024/12/25/4040example2drawio.png" style="width: 762px; height: 41px;" />
30 * 
31 * 	The first and last arrangements have a total Manhattan distance of 1 + 1 + 2 = 4.
32 * 	The middle two arrangements have a total Manhattan distance of 1 + 2 + 3 = 6.
33 * 
34 * The total Manhattan distance between all pairs of pieces across all arrangements is 4 + 6 + 6 + 4 = 20.
35 * </div>
36 *  
37 * Constraints:
38 * 
39 * 	1 <= m, n <= 10^5
40 * 	2 <= m * n <= 10^5
41 * 	<font face="monospace">2 <= k <= m * n</font>
42 * 
43 */
44pub struct Solution {}
45
46// problem: https://leetcode.com/problems/manhattan-distances-of-all-arrangements-of-pieces/
47// discuss: https://leetcode.com/problems/manhattan-distances-of-all-arrangements-of-pieces/discuss/?currentPage=1&orderBy=most_votes&query=
48
49// submission codes start here
50
51impl Solution {
52    pub fn distance_sum(m: i32, n: i32, k: i32) -> i32 {
53        0
54    }
55}
56
57// submission codes end
58
59#[cfg(test)]
60mod tests {
61    use super::*;
62
63    #[test]
64    fn test_3426() {
65    }
66}
67