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] Số Narayana N(n,k)

    Số Narayana đếm số đường đi Dyck độ dài 2n2n2n có đúng kkk đỉnh cực đại (peak), cho bởi công thức

    N(n,k)=1n(nk)(nk−1).N(n,k)=\frac{1}{n}\binom{n}{k}\binom{n}{k-1}.N(n,k)=n1​(kn​)(k−1n​).

    Tổng theo kkk của N(n,k)N(n,k)N(n,k) chính là số Catalan CnC_nCn​. Cho n,kn,kn,k, in N(n,k)N(n,k)N(n,k). Quy ước N(0,0)=1N(0,0)=1N(0,0)=1. Kết quả vừa với số nguyên, không cần modulo.

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

      Một dòng chứa hai số nguyên nnn và kkk.

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

      0≤n≤300 \le n \le 300≤n≤30, 0≤k≤300 \le k \le 300≤k≤30.

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

      Một dòng: giá trị N(n,k)N(n,k)N(n,k).

    Ví dụ:

    Đầu vào:

    4 2

    Đầu ra:

    6

    Giải thích:

    $N(4,2)=\frac{1}{4}\binom{4}{2}\binom{4}{1}=\frac{1}{4}\cdot 6\cdot 4=6$.

    Đang tải editor...