Skip to content

3426. Manhattan Distances of All Arrangements of Pieces

SourceBiweekly Contest 148 Q4DifficultyHardRating2443

Description

You are given three integers m, n, and k.

There is a rectangular grid of size m × n containing k identical pieces. Return the sum of Manhattan distances between every pair of pieces over all valid arrangements of pieces.

A valid arrangement is a placement of all k pieces on the grid with at most one piece per cell.

Since the answer may be very large, return it modulo 109 + 7.

The Manhattan Distance between two cells (xi, yi) and (xj, yj) is |xi - xj| + |yi - yj|.

 

Example 1:

Input: m = 2, n = 2, k = 2

Output: 8

Explanation:

The valid arrangements of pieces on the board are:

  • In the first 4 arrangements, the Manhattan distance between the two pieces is 1.
  • In the last 2 arrangements, the Manhattan distance between the two pieces is 2.

Thus, the total Manhattan distance across all valid arrangements is 1 + 1 + 1 + 1 + 2 + 2 = 8.

Example 2:

Input: m = 1, n = 4, k = 3

Output: 20

Explanation:

The valid arrangements of pieces on the board are:

  • The first and last arrangements have a total Manhattan distance of 1 + 1 + 2 = 4.
  • The middle two arrangements have a total Manhattan distance of 1 + 2 + 3 = 6.

The total Manhattan distance between all pairs of pieces across all arrangements is 4 + 6 + 6 + 4 = 20.

 

Constraints:

  • 1 <= m, n <= 105
  • 2 <= m * n <= 105
  • 2 <= k <= m * n

Solutions

Solution 1

Thinking

We place \(k\) pieces on an \(m\times n\) board and sum Manhattan distances over all placements. Both the number of cells and \(k\) can reach \(10^5\), so combinations cannot be listed.

Manhattan distance splits into row and column parts. Contribution inside a row (column) depends only on how many cells of that line are chosen; contribution between lines depends on the index gap and the ways to finish the remaining pieces.

For rows \(i<j\) the term is \((j-i)\) times \(n^2\,C_{mn-2}^{k-2}\) with the usual pair multiplicity; columns are symmetric. After combination tables the sum is \(O(m+n)\).

1


1


1


1

Comments