Manhattan Distances of All Arrangements of Pieces

• Calculate N = m * n, the total number of cells.
• If k < 2, return 0 as no pairs of pieces can be formed.
• Initialize a variable total_dist_sum to store the sum of Manhattan distances between all pairs of distinct cells.
• Use four nested loops to iterate through every possible pair of distinct cells (r1, c1) and (r2, c2) on the m x n grid.
• For each pair, calculate the Manhattan distance |r1 - r2| + |c1 - c2| and add it to total_dist_sum.
• Since each pair is counted twice in the loops (e.g., (c1, c2) and (c2, c1)), divide total_dist_sum by 2.
• Precompute factorials and their modular inverses to calculate combinations efficiently.
• Calculate the number of ways to place the remaining k-2 pieces in the remaining N-2 cells, which is C(N-2, k-2).
• The final answer is (total_dist_sum * C(N-2, k-2)) % MOD.

The core idea is to calculate the sum of Manhattan distances between every pair of distinct cells on the grid, let's call it Sum_Dist_Cells. The final answer is then Sum_Dist_Cells multiplied by the number of ways to choose the other k-2 pieces from the remaining m*n - 2 cells.

• Step 1: Sum of Distances Between All Cell Pairs We can use four nested loops to iterate through all pairs of cells c1 = (r1, c1) and c2 = (r2, c2). For each pair where c1 != c2, we add |r1 - r2| + |c1 - c2| to a running total. To avoid double-counting, we can divide the final sum by 2.

• Step 2: Count Arrangements For any given pair of cells c1 and c2, if we place pieces on them, we still need to place k-2 more pieces on the grid. The number of available cells is m*n - 2. The number of ways to do this is given by the binomial coefficient C(m*n - 2, k - 2).

• Step 3: Final Calculation The total sum over all arrangements is (Sum_Dist_Cells * C(m*n - 2, k - 2)) % MOD.

Here is a conceptual code snippet for calculating Sum_Dist_Cells:

1// This approach is too slow and will time out.2// It's for conceptual understanding.3long totalDist = 0;4long N = (long)m * n;5long MOD = 1_000_000_007;6 7for (int r1 = 0; r1 < m; r1++) {8    for (int c1 = 0; c1 < n; c1++) {9        for (int r2 = 0; r2 < m; r2++) {10            for (int c2 = 0; c2 < n; c2++) {11                if (r1 == r2 && c1 == c2) continue;12                totalDist = (totalDist + Math.abs(r1 - r2) + Math.abs(c1 - c2));13            }14        }15    }16}17 18// Each pair is counted twice, so divide by 219// In modular arithmetic, we multiply by the modular inverse of 2.20long inv2 = power(2, MOD - 2); // Assuming a modular exponentiation function 'power'21totalDist = (totalDist * inv2) % MOD;22 23// Precompute factorials and their inverses to calculate combinations24precomputeFactorials((int)N);25long combinations = nCr_mod_p(N - 2, k - 2); // Assuming a combination function 'nCr_mod_p'26 27long ans = (totalDist * combinations) % MOD;

• The total sum is C(N-2, k-2) * (SumX + SumY), where N = m*n.
• SumX is the sum of row differences |r1 - r2| over all distinct cell pairs, and SumY is for column differences.
• SumX can be expressed as n^2 * (sum of |i-j| for all pairs of rows i, j).
• Calculate sum_diff_m = Sum_{0 <= i < j < m} (j-i) using two nested loops, which takes O(m^2) time.
• Then SumX = n^2 * sum_diff_m.
• Similarly, calculate sum_diff_n = Sum_{0 <= i < j < n} (j-i) in O(n^2) time.
• Then SumY = m^2 * sum_diff_n.
• Combine the results and multiply by C(N-2, k-2).

We build upon the insight that the total sum is C(N-2, k-2) * (SumX + SumY), where SumX and SumY are the sums of absolute differences of row and column indices, respectively, over all pairs of distinct cells.

• Calculating SumX The sum SumX = Sum_{c1 != c2} |r1 - r2|. A pair of cells from rows i and j contributes |i-j| to this sum. For any two distinct rows i and j, there are n cells in each, forming n*n pairs of cells. Thus, the total contribution from these two rows is n^2 * |i-j|. SumX = Sum_{0 <= i < j < m} n^2 * (j-i). We can calculate Sum_{0 <= i < j < m} (j-i) with nested loops.

• Calculating SumY Symmetrically, SumY = Sum_{0 <= i < j < n} m^2 * (j-i).

• Complexity Calculating the sum of differences for rows takes O(m^2) and for columns takes O(n^2). Precomputing factorials takes O(m*n). The total time complexity is O(m*n + m^2 + n^2).

Example code snippet for this logic:

1long N = (long)m * n;2long MOD = 1_000_000_007;3 4// Calculate SumX5long sum_diff_m = 0;6for (long i = 0; i < m; i++) {7    for (long j = i + 1; j < m; j++) {8        sum_diff_m = (sum_diff_m + (j - i)) % MOD;9    }10}11long m_long = m;12long n_long = n;13long sumX = (n_long * n_long % MOD * sum_diff_m) % MOD;14 15// Calculate SumY16long sum_diff_n = 0;17for (long i = 0; i < n; i++) {18    for (long j = i + 1; j < n; j++) {19        sum_diff_n = (sum_diff_n + (j - i)) % MOD;20    }21}22long sumY = (m_long * m_long % MOD * sum_diff_n) % MOD;23 24long totalDist = (sumX + sumY) % MOD;25 26// Calculate combinations and final answer as in other approaches27long combinations = nCr_mod_p(N - 2, k - 2, fact, invFact, MOD);28long ans = (totalDist * combinations) % MOD;

• The total sum is C(N-2, k-2) * (SumX + SumY), where N = m*n.
• Recognize that the sum S_d = Sum_{0 <= i < j < d} (j-i) has a closed-form formula: S_d = (d^3 - d) / 6.
• Calculate SumX = n^2 * S_m = n^2 * (m^3 - m) / 6.
• Calculate SumY = m^2 * S_n = m^2 * (n^3 - n) / 6.
• All calculations must be performed using modular arithmetic. Division by 6 is done by multiplying with the modular multiplicative inverse of 6.
• The term d^3 - d = d(d-1)(d+1) is a product of three consecutive integers, so it is always divisible by 6, ensuring the division is valid over integers.
• Precompute factorials up to N to find C(N-2, k-2) in O(1) time.
• Combine the terms to get the final answer.

This method is based on the same reframing as the previous approaches but uses a mathematical formula for an efficient calculation.

• The Formula The total sum is TotalSum = C(N-2, k-2) * (SumX + SumY) % MOD. SumX = n^2 * (Sum_{0 <= i < j < m} (j-i)) SumY = m^2 * (Sum_{0 <= i < j < n} (j-i))

• Closed-Form for Sum of Differences The sum Sum_{0 <= i < j < d} (j-i) can be proven to be equal to (d^3 - d) / 6. Therefore, we can calculate SumX and SumY in O(1) time (with large number arithmetic). SumX = n^2 * (m^3 - m) / 6 SumY = m^2 * (n^3 - n) / 6

• Modular Arithmetic Since we need the result modulo 10^9 + 7, all calculations must be done modulo this prime. Division by 6 is handled by multiplying by the modular inverse of 6, which can be calculated using Fermat's Little Theorem: 6^(MOD-2) % MOD.

• Implementation The overall algorithm involves precomputing factorials up to N = m*n, calculating the modular inverse of 6, and then plugging the values of m and n into the formulas for SumX and SumY.

Here is a complete Java implementation:

1class Solution {2    private static final int MOD = 1_000_000_007;3    private long[] fact;4    private long[] invFact;5 6    public int sumOfManhattanDistances(int m, int n, int k) {7        if (k < 2) {8            return 0;9        }10        long N = (long) m * n;11 12        precomputeFactorials((int)N);13 14        long combinations = nCr_mod_p(N - 2, k - 2);15 16        long m_long = m;17        long n_long = n;18 19        long inv6 = power(6, MOD - 2);20 21        // Calculate sum of differences for rows: (m^3 - m) / 622        long term_m = (m_long * (m_long - 1)) % MOD;23        term_m = (term_m * (m_long + 1)) % MOD;24        term_m = (term_m * inv6) % MOD;25 26        // Calculate sum of differences for columns: (n^3 - n) / 627        long term_n = (n_long * (n_long - 1)) % MOD;28        term_n = (term_n * (n_long + 1)) % MOD;29        term_n = (term_n * inv6) % MOD;30 31        // SumX = n^2 * term_m32        long sumX = (n_long * n_long % MOD * term_m) % MOD;33        34        // SumY = m^2 * term_n35        long sumY = (m_long * m_long % MOD * term_n) % MOD;36 37        long totalDist = (sumX + sumY) % MOD;38 39        long ans = (combinations * totalDist) % MOD;40        return (int) ans;41    }42 43    private void precomputeFactorials(int maxN) {44        fact = new long[maxN + 1];45        invFact = new long[maxN + 1];46        fact[0] = 1;47        invFact[0] = 1;48        for (int i = 1; i <= maxN; i++) {49            fact[i] = (fact[i - 1] * i) % MOD;50            invFact[i] = power(fact[i], MOD - 2);51        }52    }53 54    private long power(long base, long exp) {55        long res = 1;56        base %= MOD;57        while (exp > 0) {58            if (exp % 2 == 1) res = (res * base) % MOD;59            base = (base * base) % MOD;60            exp /= 2;61        }62        return res;63    }64 65    private long nCr_mod_p(long n, long r) {66        if (r < 0 || r > n) {67            return 0;68        }69        return (((fact[(int)n] * invFact[(int)r]) % MOD) * invFact[(int)(n - r)]) % MOD;70    }71}