Chương trình đếm số cây BST duy nhất từ 0 đến n-1 trong Python

Cho số n, đếm số cây BST duy nhất có thể tạo từ các giá trị [0, n). Kết quả modulo 10^9+7.

Ví dụ

Đầu vào: n = 3.
Đầu ra: 5 (số Catalan).

Thuật toán

1. Sử dụng công thức Catalan: C_n = (2n choose n) / (n+1).
2. Tính tử số và mẫu số modulo m = 10^9+7 bằng lặp.
3. Áp dụng nghịch modulo Fermat: numer * denom^(m-2) mod m.

Mã nguồn Python

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

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

Đầu vào / Đầu ra

Input: 4
Output: 14