To solve this problem, we need to count the number of ways to place K stones in an N x M grid such that no two stones share the same row or column.

Approach

1. Problem Analysis:

   • We need to choose K distinct rows from N rows, which can be done in C(N, K) ways (combination).
   • For these K rows, we need to assign each to a distinct column from M columns, which can be done in P(M, K) ways (permutation).
   • The total number of ways is the product of these two values modulo (10^9 + 7).

2. Key Observations:

   • If K > min(N, M), the result is zero because we can't place K stones without sharing rows or columns.
   • We use factorials and inverse factorials to efficiently compute combinations and permutations modulo (10^9 +7).

3. Precomputation:

   • Precompute factorials up to the maximum possible value of N or M (1e5) to quickly calculate combinations and permutations.
   • Precompute inverse factorials using Fermat's Little Theorem for modular inverses.

Solution Code

MOD = 10**9 + 7
MAX = 10**5 + 10  # Since N and M are up to 1e5

# Precompute factorials
fact = [1] * MAX
for i in range(1, MAX):
    fact[i] = fact[i-1] * i % MOD

# Precompute inverse factorials using Fermat's Little Theorem
inv_fact = [1] * MAX
inv_fact[MAX-1] = pow(fact[MAX-1], MOD-2, MOD)
for i in range(MAX-2, -1, -1):
    inv_fact[i] = inv_fact[i+1] * (i+1) % MOD

# Read input
N, M, K = map(int, input().split())

if K > N or K > M:
    print(0)
else:
    # Calculate combination C(N, K)
    comb = fact[N] * inv_fact[K] % MOD
    comb = comb * inv_fact[N - K] % MOD

    # Calculate permutation P(M, K) = M!/(M-K)!
    perm = fact[M] * inv_fact[M - K] % MOD

    # Total ways
    ans = comb * perm % MOD
    print(ans)

Explanation

• Factorial Precomputation: We compute factorials up to 1e5 to avoid recalculating them for each query.
• Inverse Factorial: Using Fermat's Little Theorem, we compute the inverse of each factorial, which helps in calculating combinations efficiently.
• Combination Calculation: (C(N, K) = \frac{N!}{K! \times (N-K)!}) modulo (10^9 +7).
• Permutation Calculation: (P(M, K) = \frac{M!}{(M-K)!}) modulo (10^9 +7).
• Result: The product of the combination and permutation gives the total number of valid ways to place K stones.

This approach ensures that we handle large values efficiently and correctly using modular arithmetic. The precomputation steps run in O(MAX) time, and each query is answered in O(1) time, making the solution scalable for large inputs.

作者声明:本文包含人工智能生成内容。