ধরুন আমাদের একটি সংখ্যা n আছে, আমাদেরকে [0, n) থেকে সংখ্যা দিয়ে তৈরি করতে পারি এমন অনন্য BST-এর সংখ্যা খুঁজে বের করতে হবে। উত্তরটি খুব বড় মোড হলে ফলাফল 10^9+7
সুতরাং, যদি ইনপুট n =3 এর মত হয়, তাহলে আউটপুট হবে 5
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- সংখ্যা :=1
- ডিনম :=n + 1
- 1 থেকে n রেঞ্জের জন্য, করুন
- সংখ্যা :=সংখ্যা * n + i
- সংখ্যা :=সংখ্যা মোড m
- ডিনম :=ডিনোম * i
- denom :=denom mod m
- সংখ্যা :=সংখ্যা * (denom^(m-2)) mod m
- রিটার্ন সংখ্যা মোড 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
