GRNUM - Đánh số đồ thị
Giới hạn- Thời gian: 2.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Cho một đơn đồ thị vô hướng gồm K x N đỉnh, các đỉnh được chia thành K nhóm, mỗi nhóm có N đỉnh. Các nhóm được đặt tên bằng các chữ cái in hoa A, B, C, ... các đỉnh tương ứng thuộc các nhóm được đặt tên bằng các số từ 0 đến N – 1. Giả sử Ch K là chữ cái ứng với nhóm thứ K, ta quy ước chữ cái tiếp sau A là B, tiếp sau B là C, … tiếp sau Ch K là A và ký hiệu chữ cái tiếp sau Ch là next(Ch). Đồ thị này có các tính chất sau:
Giữa các đỉnh thuộc cùng một nhóm không có cạnh nối.
Các đỉnh thuộc 2 nhóm bất kỳ có tên là Ch và next(Ch) có đúng N cạnh nối từ đỉnh thuộc nhóm Ch đến đỉnh thuộc nhóm next(Ch).
Bạn cần được yêu cầu đánh số các đỉnh của đồ thị sao cho:
Các đỉnh thuộc 1 nhóm được đánh các số là hoán vị của các số tự nhiên từ 0 đến N – 1.
Với 2 nhóm Ch và next(Ch) bất kỳ thì N số trên N cạnh nối các đỉnh thuộc chúng là khác nhau. Nếu đỉnh i thuộc nhóm Ch được đánh số là P kề với đỉnh j thuộc nhóm next(Ch) được đánh số là Q thì cạnh nối 2 đỉnh này được đánh số là (N + P – Q) mod N.
Biết rằng 2 cách đánh số các đỉnh của đồ thị được coi là khác nhau nếu trong 2 cách đánh số, tồn tại một đỉnh thuộc một nhóm nào đó được đánh số khác nhau. Bạn hãy tính số cách đánh số khác nhau.
Input
Dòng thứ nhất ghi 2 số nguyên dương K và N là số nhóm và số đỉnh thuộc 1 nhóm.
Mỗi dòng trong K x N dòng tiếp theo ghi 1 cạnh của đồ thị theo dạng Ch i j trong đó Ch là một ký tự, i và j là 2 số nguyên với ý nghĩ có cạnh nối từ đỉnh i của nhóm Ch đến đỉnh j của nhóm next(Ch).
Output
Ghi ra duy nhất một số nguyên là số lượng cách đánh số khác nhau tìm được.
Example
Input: 3 3 A 0 0 A 1 2 A 2 1 B 1 0 B 1 2 B 2 2 C 0 2 C 1 1 C 1 2 Output: 54 Giới hạn: 1 ≤ K ≤ 5 1 ≤ N ≤ 20 Số cách đánh số khác nhau luôn đảm bảo không quá 1000000
- Người up: cun
- Nguồn bài: Ioicamp - marathon 06 - 07