Chương trình đếm số ma trận khiêm tốn có thể có trong Python

Giả sử chúng ta có hai giá trị n và m. Chúng ta phải tìm số cách sắp xếp có thể có của ma trận nhỏ bậc n x m. Ma trận được cho là khiêm tốn khi

Nó chứa mỗi phần tử trong phạm vi từ 1 đến n x m đúng một lần
đối với hai cặp chỉ số bất kỳ (i1, j1) và (i2, j2), nếu (i1 + j1) <(i2 + j2), thì Mat [i1, j1]

Nếu câu trả lời quá lớn thì trả về kết quả mod 10 ^ 9 + 7.

Vì vậy, nếu đầu vào là n =2 m =2, thì đầu ra sẽ là 2, vì có thể có hai ma trận -

1	2
3	4

Và

1	3
2	4

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

p:=10 ^ 9 + 7
kết quả:=một danh sách có giá trị 1
đối với x trong phạm vi từ 2 đến 10 ^ 6, thực hiện
- temp:=phần tử cuối cùng của kết quả
- temp:=(temp * x) mod p
- chèn tạm thời vào cuối kết quả
nếu m> n, thì
- tạm thời:=n
- n:=m
- m:=temp
prod:=1
đối với x trong phạm vi từ 1 đến m, thực hiện
- prod:=(prod * result [x-1]) mod p
- prod:=(prod ^ 2) mod p
đối với x trong phạm vi từ 0 đến n - m, thực hiện
- prod:=(prod * result [m-1]) mod p
sản phẩm trả lại

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

p = 10**9+7

def solve(n, m):
   result = [1]
   for x in range(2,10**6+1):
      temp = result[-1]
      temp = (temp*x) % p
      result.append(temp)

   if(m > n):
      temp = n
      n = m
      m = temp
   prod = 1
   for x in range(1,m):
      prod = (prod * result[x-1]) % p
   prod = (prod**2) % p
   for x in range(n-m+1):
      prod = (prod*result[m-1]) % p
   return prod

n = 3
m = 3
print(solve(n, m))

Đầu vào

3, 3

Chương trình đếm số ma trận khiêm tốn có thể có trong Python

Ví dụ

Đầu vào

Đầu ra