สมมติว่าเรามีตัวเลขหนึ่งตัว n เราต้องหาจำนวน BST ที่ไม่ซ้ำกันซึ่งเราสามารถสร้างขึ้นด้วยตัวเลขตั้งแต่ [0, n) หากคำตอบคือ mod ที่ใหญ่มาก ผลลัพธ์จะเป็น 10^9+7
ดังนั้นหากอินพุตเท่ากับ n =3 เอาต์พุตจะเป็น 5
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ตัวเลข :=1
- ค่า :=n + 1
- สำหรับฉันในช่วง 1 ถึง n ทำ
- ตัวเลข :=ตัวเลข * n + ผม
- ตัวเลข :=ตัวเลข mod m
- denom :=denom * i
- denom :=denom mod m
- ตัวเลข :=ตัวเลข * (denom^(m-2)) mod m
- คืนค่าจำนวน mod 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
