Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Toán rời rạc] Đếm cây nhị phân bằng truy hồi Catalan

    Đếm số cây nhị phân khác nhau có n nút bằng công thức truy hồi Catalan: C_0 = 1, C_n = Σ_{j=0..n-1} C_j · C_{n-1-j}. Tính bằng quy hoạch động, lấy modulo 10^9+7.

    • Định dạng đầu vào:

      Một dòng chứa n.

    • Ràng buộc đầu vào:

      0 ≤ n ≤ 5000.

    • Định dạng đầu ra:

      Số cây nhị phân n nút modulo 10^9+7.

    Ví dụ:

    Đầu vào:

    3

    Đầu ra:

    5

    Giải thích:

    C_3 = C0·C2 + C1·C1 + C2·C0 = 2+1+2 = 5.

    Đang tải editor...