Tap here to switch tabs
Problem
Submissions

Problem: Manhattan Distances of All Arrangements of Pieces

Manhattan Distances of All Arrangements of Pieces asks for the total Manhattan distance across every pair of pieces in every way to place k identical pieces on an m by n grid, modulo a large prime.

Statement

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

Consider an m by n grid where k identical pieces are placed such that each cell contains at most 11 piece.

The Manhattan distance between two cells at coordinates (r1,c1)(r_1, c_1) and (r2,c2)(r_2, c_2) is defined as ∣r1−r2∣+∣c1−c2∣|r_1 - r_2| + |c_1 - c_2|.

Return the total sum of Manhattan distances between all pairs of pieces across all valid arrangements. Since the answer may be very large, return it modulo 109+710^9 + 7.

Constraints:

  • 1≤1 \leq m, n ≤105\leq 10^5

  • 2≤2 \leq m ×\times n ≤105\leq 10^5

  • 2≤2 \leq k ≤\leq m ×\times n

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Manhattan Distances of All Arrangements of Pieces

Manhattan Distances of All Arrangements of Pieces asks for the total Manhattan distance across every pair of pieces in every way to place k identical pieces on an m by n grid, modulo a large prime.

Statement

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

Consider an m by n grid where k identical pieces are placed such that each cell contains at most 11 piece.

The Manhattan distance between two cells at coordinates (r1,c1)(r_1, c_1) and (r2,c2)(r_2, c_2) is defined as ∣r1−r2∣+∣c1−c2∣|r_1 - r_2| + |c_1 - c_2|.

Return the total sum of Manhattan distances between all pairs of pieces across all valid arrangements. Since the answer may be very large, return it modulo 109+710^9 + 7.

Constraints:

  • 1≤1 \leq m, n ≤105\leq 10^5

  • 2≤2 \leq m ×\times n ≤105\leq 10^5

  • 2≤2 \leq k ≤\leq m ×\times n