Đếm số ma trận "humble" cấp n x m trong Python

Ma trận n x m gọi là humble nếu chứa mỗi số 1..n*m đúng một lần, và với bất kỳ (i1,j1), (i2,j2): nếu i1+j1 < i2+j2 thì Mat[i1][j1] < Mat[i2][j2]. Đếm số ma trận humble, modulo 10^9+7.

Ví dụ: n=2, m=2 → 2 ma trận.

Giải thuật

• Điều kiện có nghĩa là các đường chéo (i+j = const) phải tăng dần theo tổng chỉ số.
• Số ma trận = tích giai thừa của độ dài các đường chéo.
• Tính trước giai thừa modulo 10^9+7 đến 10^6.
• Nếu m > n, hoán đổi.
• Kết quả = (∏_{x=1}^{m-1} (x!)^2) * ( (m-1)! )^{n-m+1} mod p.

Ví dụ mã Python

p = 10**9 + 7

def solve(n, m):
    fact = [1]
    for x in range(2, 10**6 + 1):
        fact.append(fact[-1] * x % p)
    if m > n:
        n, m = m, n
    prod = 1
    for x in range(1, m):
        prod = prod * fact[x - 1] % p
        prod = prod * prod % p
    for _ in range(n - m + 1):
        prod = prod * fact[m - 1] % p
    return prod

n = 3
m = 3
print(solve(n, m))  # Output: 24

Đầu vào

3, 3

Đầu ra

24