পাইথনে ০ থেকে n মান দিয়ে ইউনিক BST-এর সংখ্যা গণনা করার প্রোগ্রাম

মনে করুন n একটি সংখ্যা। [0, n) রেঞ্জের সংখ্যা দিয়ে কতগুলো ইউনিক BST তৈরি করা যায় সেটি খুঁজে বের করতে হবে। উত্তর বড় হলে 10⁹+৭ দিয়ে মড করুন। (ক্যাটালান নম্বর)।

উদাহরণস্বরূপ, n=3 হলে আউটপুট ৫। ছবি দেওয়া আছে।

সমাধানের ধাপসমূহ

• numer := 1, denom := n+1
• i = 1 থেকে n পর্যন্ত,
  • numer *= n+i; numer %= m
  • denom *= i; denom %= m
• numer *= pow(denom, m-2, m); numer %= m
• numer % m ফেরত দিন

উদাহরণ

class Solution:
    def solve(self, n):
        m = 10 ** 9 + 7
        numer = 1
        denom = n + 1
        for i in range(1, n + 1):
            numer *= n + i
            numer %= m
            denom *= i
            denom %= m
        numer *= pow(denom, m-2, m)
        return numer % m

ob = Solution()
print(ob.solve(4))

ইনপুট

4

আউটপুট

14