PreVOI 2025 - Contest 2 - Bảng vuông
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Cho một bảng vuông kích thước ~N \times M~, các hàng được đánh số từ ~1~ đến ~N~, các cột được đánh số từ ~1~ đến ~M~. Mỗi ô trên bảng sẽ được điền vào một trong hai giá trị ~0~ hoặc ~1~ sao cho bất kỳ bảng con kích thước ~2 \times 2~ nào cũng chứa chẵn giá trị ~1~.
Có thêm ~T~ ràng buộc yêu cầu rằng giá trị của ô nằm ở hàng ~u~ cột ~v~ phải là ~x~.
Hãy đếm xem có bao nhiêu cách điền các giá trị vào để thoả mãn tất cả điều kiện.
Input
Dòng đầu tiên chứa ba số nguyên ~N, M, T~ ~(1 \le N, M \le 10^9; 0 \le T \le \min(10^5, N \cdot M))~ lần lượt thể hiện số hàng của bảng, số cột của bảng và số ràng buộc thêm.
~T~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u_i, v_i, x_i~ ~(1 \le u_i \le N; 1 \le v_i \le M; 0 \le x_i \le 1)~ thể hiện một ràng buộc.
Output
Gồm một dòng duy nhất chứa một số nguyên thể hiện số cách điền giá trị thoả mãn.
Vì kết quả có thể rất lớn nên hãy ghi ra phần dư của kết quả khi chia cho ~10^9 + 9999~.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~10\%~ | ~N \cdot M \le 20~. |
| 2 | ~10\%~ | ~T = 0~. |
| 3 | ~10\%~ | ~T = 1~. |
| 4 | ~10\%~ | ~T = 2~. |
| 5 | ~20\%~ | ~N \le 1000~; ~M \le 8~. |
| 6 | ~20\%~ | ~N, M \le 10^5~. |
| 7 | ~20\%~ | Không có giới hạn gì thêm |
Sample Input 1
2 2 2
1 1 0
2 2 0
Sample Output 1
2
Bình luận