পাইথনে হাম্বল ম্যাট্রিক্সের সম্ভাব্য অরেঞ্জমেন্টের সংখ্যা বের করা

n×m অর্ডারের হাম্বল ম্যাট্রিক্সের সম্ভাব্য অরেঞ্জমেন্ট কতটি আছে তা বের করতে হবে। হাম্বল ম্যাট্রিক্সের শর্ত:

১ থেকে n×m পর্যন্ত প্রতিটি সংখ্যা ঠিক একবার থাকবে।
যেকোনো দুটি ইনডেক্স জোড়া (i1,j1) এবং (i2,j2) এর জন্য যদি i1+j1 < i2+j2 হয়, তবে Mat[i1,j1] < Mat[i2,j2] হবে।

উত্তর ১০⁹+৭ মডুলো।

উদাহরণ

ইনপুট: n = 2, m = 2

আউটপুট: 2

সম্ভাব্য ম্যাট্রিক্স:

1	2
3	4

এবং

1	3
2	4

সমাধান পদ্ধতি

p := 10⁹+7
ফ্যাক্টোরিয়াল প্রিকম্পিউট করুন ১০⁶ পর্যন্ত।
যদি n হয় তবে সোয়্যাপ করুন।
prod := 1
x = 1 থেকে m-1: prod = (prod * fact[x-1]) % p; prod = (prod**2) % p
x = 0 থেকে n-m: prod = (prod * fact[m-1]) % p
prod রিটার্ন করুন।

পাইথন ইমপ্লিমেন্টেশন

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 x in range(n - m + 1):
        prod = (prod * fact[m - 1]) % p
    return prod

# টেস্ট
n = 3
m = 3
print(solve(n, m))  # আউটপুট: 24

ইনপুট

3, 3