โปรแกรมนับจำนวนเมทริกซ์ที่ต่ำต้อยที่เป็นไปได้ใน Python

สมมติว่าเรามีสองค่า n และ m เราต้องหาจำนวนการจัดเรียงที่เป็นไปได้ของเมทริกซ์ต่ำต้อยของคำสั่ง n x m กล่าวกันว่าเมทริกซ์มีความอ่อนน้อมถ่อมตนเมื่อ

ประกอบด้วยแต่ละองค์ประกอบในช่วง 1 ถึง n x m เพียงครั้งเดียว
สำหรับคู่ดัชนีสองคู่ (i1, j1) และ (i2, j2) ถ้า (i1 + j1) <(i2 + j2) แล้ว Mat[i1, j1]

หากคำตอบมีขนาดใหญ่เกินไป ให้ส่งคืนผลลัพธ์ mod 10^9 + 7

ดังนั้น หากอินพุตเป็น n =2 m =2 เอาต์พุตจะเป็น 2 เนื่องจากมีเมทริกซ์ที่เป็นไปได้สองอัน -

1	2
3	4

และ

1	3
2	4

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

p :=10^9+7
ผลลัพธ์ :=รายการที่มีค่า 1
สำหรับ x ในช่วง 2 ถึง 10^6 ให้ทำ
- temp :=องค์ประกอบสุดท้ายของผลลัพธ์
- temp :=(temp*x) mod p
- ใส่ temp ที่ส่วนท้ายของผลลัพธ์
ถ้า m> n แล้ว
- อุณหภูมิ :=n
- น :=ม
- ม :=อุณหภูมิ
ผลผลิต :=1
สำหรับ x ในช่วง 1 ถึง m ให้ทำ
- prod :=(prod * result[x-1]) mod p
- prod :=(prod^2) mod p
สำหรับ x ในช่วง 0 ถึง n - m ทำ
- prod :=(prod * result[m-1]) mod p
คืนสินค้า

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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))

อินพุต

3, 3