Các lượt nộp

Danh sách bài

Báo lỗi

solution

Đề bài: [Toán rời rạc] Số Catalan

Số Catalan $C_n$ đếm nhiều cấu trúc: số cây nhị phân $n$ nút, số cách đặt ngoặc đúng với $n$ cặp ngoặc, số đường đi Dyck... Công thức:

$C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!\,n!}.$

Cho $n$ , hãy tính $C_n \bmod (10^9+7)$ .

Ví dụ: $C_3 = \frac{1}{4}\binom{6}{3} = \frac{20}{4} = 5$ .

Định dạng đầu vào:
Một dòng gồm một số nguyên $n$ .
Ràng buộc đầu vào:
$0 \le n \le 10^6$ .
Định dạng đầu ra:
Một dòng: $C_n \bmod (10^9+7)$ .

Ví dụ:

Đầu vào:

3

Đầu ra:

5

Giải thích:

$C_3=\frac{1}{4}\binom{6}{3}=\frac{20}{4}=5$.

Đang tải editor...