Tô màu đa giác
Đề bài
Mô tả
Cho một đa giác lồi có đỉnh, các đỉnh được đánh số từ đến theo chiều kim đồng hồ. Một đường chéo là một đoạn thẳng nối hai đỉnh không kề nhau của đa giác. Nói cách khác, một đường chéo nối hai đỉnh và của đa giác với .
Bài toán gồm hai bước:
- Đầu tiên, bạn cần chia đa giác thành tam giác bằng đường chéo. Mỗi cách chia hợp lệ được xác định duy nhất bởi một tập đường chéo của đa giác sao cho các đường chéo được chọn chỉ cắt nhau tại đầu mút. Nói cách khác, nếu hai đường chéo của một cách chia hợp lệ có điểm chung thì điểm chung đó phải là một đỉnh của đa giác. Cho trước đường chéo , bạn cần tìm thêm đường chéo khác để tạo thành một cách chia hợp lệ.
- Sau đó, bạn cần tô màu cả tam giác bằng màu (đánh số từ đến ), sao cho mỗi tam giác được tô đúng một màu và hai tam giác có chung một cạnh phải được tô khác màu.
Với là một cách chia hợp lệ có thể nhận được ở bước một, gọi là số cách tô màu các tam giác ở bước hai. Bạn cần tính hai giá trị:
- , tức là số cách tô màu hợp lệ nhỏ nhất ở bước hai, xét trên mọi cách chia hợp lệ ở bước một.
- là số cách chia hợp lệ thỏa mãn ; nói cách khác, là số cách chia hợp lệ ở bước một cho số cách tô màu nhỏ nhất ở bước hai.
Dữ liệu vào
- Dòng đầu tiên chứa ba số nguyên , và .
- dòng tiếp theo, dòng thứ chứa hai số nguyên và () mô tả một đường chéo nối hai đỉnh và của đa giác.
Dữ liệu đảm bảo đường chéo này chỉ cắt nhau tại đầu mút.
Dữ liệu ra
In ra hai số nguyên trên một dòng: giá trị và . Vì các giá trị này có thể rất lớn, hãy in chúng theo modulo .
Ràng buộc
- .
- .
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 0 2 | 2 2 | Hình vuông có cách chia (theo đường chéo hoặc ), mỗi cách chia cho tam giác kề nhau và có cách tô bằng màu. |
| 6 3 3 2 4 4 6 6 2 |
24 1 | Ba đường chéo đã cho tạo thành cách chia duy nhất gồm tam giác: tam giác ở giữa kề với ba tam giác còn lại. Tô tam giác giữa có cách, mỗi tam giác còn lại có cách: . |
Bình luận