VM 08 Bài 03 - Đếm đường đi trên đồ thị đầy đủ

Xem dạng PDF
Gửi bài giải
Điểm: 0,17 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Nguồn bài:
VNOI Marathon '08 - Round 3/DivBProblem Setter: Lê Ðôn Khuê
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Một đồ thị đầy đủ ~N~ đỉnh là đồ thị mà giữa mọi cặp đỉnh đều có cạnh nối.

Đếm số đường đi giữa đỉnh ~1~ và đỉnh ~2~ của đồ thị.

Lưu ý rằng một đường đi không được đi qua một đỉnh quá một lần.

Input

Ghi duy nhất một số N là số đỉnh của đồ thị ~(2 \le N \le 1000)~.

Output

In ra một số duy nhất là số lượng đường đi giữa 2 đỉnh bất kì.

Sample Input

4

Sample Output

5

Note

Giữa ~2~ đỉnh bất kì ví dụ đỉnh ~1~ và ~2~ có ~5~ đường đi:

~1-2~

~1-3-2~

~1-3-4-2~

~1-4-2~

~1-4-3-2~

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 0
    ijk  đã bình luận lúc 20, Tháng 2, 2026, 4:54

    Sol mang tính chất tham khảo:

    Vì mỗi đỉnh đều nối với nhau qua một cạnh nên số cách để từ ~1~ đến ~2~ chính là số cách chọn ~k~ đỉnh trong ~n-2~ đỉnh có hoán vị để xếp vào giữa hai đỉnh ~1~ và ~2~. Nói cách khác chính là ~\Sigma_{k=0}^{n-2} A^k_{n-2}~

    Làm sao để cái ký tự sigma nó to hẳn ra vậy mn