Introduction

In this blog post, we will explore how to solve the LeetCode problem "3426" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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

Explanation

Here's a solution to the problem, designed for efficiency and clarity.

• Key Idea: Separate the Manhattan distance calculation into row and column differences. Calculate the sum of row differences and column differences independently, then combine them. Leverage combinatorics to efficiently count arrangements.
• Optimization: Precompute factorials and their inverses modulo 10^9 + 7 to speed up the combination calculations.

• Modular Arithmetic: Perform all calculations modulo 10^9 + 7 to prevent overflow and satisfy the problem constraints.

• Runtime Complexity: O(m + n + k), where m and n are grid dimensions and k is the number of pieces. Storage Complexity: O(max(m, n)).

def solve():
    m, n, k = map(int, input().split())
    mod = 10**9 + 7

    def combinations(n, k, factorial, inverse_factorial):
        if k < 0 or k > n:
            return 0
        return (factorial[n] * inverse_factorial[k] % mod) * inverse_factorial[n - k] % mod

    def calculate_distances(length, k, factorial, inverse_factorial):
        total_distance = 0
        for i in range(length):
            count = i * (combinations(length - i - 1, k - 1, factorial, inverse_factorial) % mod) % mod
            count += (length - 1 - i) * (combinations(i, k - 1, factorial, inverse_factorial) % mod) % mod
            total_distance = (total_distance + count) % mod
        return total_distance

    max_dim = max(m, n)
    factorial = [1] * (max_dim + 1)
    inverse_factorial = [1] * (max_dim + 1)

    for i in range(2, max_dim + 1):
        factorial[i] = (factorial[i - 1] * i) % mod

    inverse_factorial[max_dim] = pow(factorial[max_dim], mod - 2, mod)
    for i in range(max_dim - 1, -1, -1):
        inverse_factorial[i] = (inverse_factorial[i + 1] * (i + 1)) % mod

    num_arrangements = combinations(m * n, k, factorial, inverse_factorial)
    row_distance_sum = (combinations(n, k, factorial, inverse_factorial) * calculate_distances(m, k, factorial, inverse_factorial)) % mod
    col_distance_sum = (combinations(m, k, factorial, inverse_factorial) * calculate_distances(n, k, factorial, inverse_factorial)) % mod

    print((row_distance_sum + col_distance_sum) % mod)


    # Code
    ```python
    def solve():    m, n, k = map(int, input().split())
    mod = 10**9 + 7

    def combinations(n, k, factorial, inverse_factorial):
        if k < 0 or k > n:
            return 0
        return (factorial[n] * inverse_factorial[k] % mod) * inverse_factorial[n - k] % mod

    def calculate_distances(length, k, factorial, inverse_factorial):
        total_distance = 0
        for i in range(length):
            count = i * (combinations(length - i - 1, k - 1, factorial, inverse_factorial) % mod) % mod
            count += (length - 1 - i) * (combinations(i, k - 1, factorial, inverse_factorial) % mod) % mod
            total_distance = (total_distance + count) % mod
        return total_distance

    max_dim = max(m, n)
    factorial = [1] * (max_dim + 1)
    inverse_factorial = [1] * (max_dim + 1)

    for i in range(2, max_dim + 1):
        factorial[i] = (factorial[i - 1] * i) % mod

    inverse_factorial[max_dim] = pow(factorial[max_dim], mod - 2, mod)
    for i in range(max_dim - 1, -1, -1):
        inverse_factorial[i] = (inverse_factorial[i + 1] * (i + 1)) % mod

    row_distance_sum = (combinations(n, k, factorial, inverse_factorial) * calculate_distances(m, k, factorial, inverse_factorial)) % mod
    col_distance_sum = (combinations(m, k, factorial, inverse_factorial) * calculate_distances(n, k, factorial, inverse_factorial)) % mod

    print((row_distance_sum + col_distance_sum) % mod)

import sys
solve()