Hoán Vị Tam Giác

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho $N$ điểm phân biệt trên mặt phẳng tọa độ, không có ba điểm nào thẳng hàng. Bessie vẽ các đoạn thẳng theo quy trình sau:

Chọn một hoán vị $p_{1}, p_{2}, \dots, p_{N}$ của $N$ điểm
Vẽ tam giác $p_{1} p_{2} p_{3}$ (3 đoạn thẳng)
Với mỗi $i$ từ 4 đến $N$ : vẽ các đoạn thẳng từ $p_{i}$ đến các điểm $p_{j}$ ( $j < i$ ) sao cho đoạn mới không cắt bất kỳ đoạn nào đã vẽ (trừ tại đầu mút)

Điều kiện: Ở mỗi bước $i \geq 4$ , phải vẽ được đúng 3 đoạn thẳng mới.

Hãy đếm số hoán vị hợp lệ, modulo $10^{9} + 7$ .

Một số nguyên: số hoán vị hợp lệ modulo $10^{9} + 7$ .

Input	Output	Giải thích
4 0 0 0 4 1 1 1 2	0	Không có hoán vị nào hợp lệ vì không thể thêm điểm thứ 4 mà tạo đúng 3 đoạn mới.
4 0 0 0 4 4 0 1 1	24	Tất cả $4! = 24$ hoán vị đều hợp lệ vì điểm $(1, 1)$ nằm trong tam giác tạo bởi 3 điểm còn lại.

Bình luận

Không có bình luận tại thời điểm này.