Phân tích

Điều đầu tiên chúng ta cần nhận thấy là nếu hai con lemming không kết thúc ở cùng một ô sau một giây, chúng sẽ không bao giờ kết thúc ở cùng một ô. Đó là bởi vì sau một giây, sẽ có đúng một con lemming trong mỗi ô, và trạng thái hoàn toàn giống như một giây trước đó.

Số lượng tổ hợp cho các hướng băng chuyền là \(2^{R \cdot C}\), vì vậy chúng ta có thể thử tất cả chúng để giải quyết bộ test nhỏ và đếm xem có bao nhiêu tổ hợp dẫn đến việc tất cả các con lemming ở các ô khác nhau sau một giây.

Để giải quyết bộ test lớn, chúng ta sẽ phải xem xét bài toán từ góc độ lý thuyết đồ thị. Giả sử chúng ta tạo ra một đồ thị hai phía như sau:

• Đối với mỗi ô \((r, c)\), tạo hai nút \(start_{r, c}\) và \(end_{r, c}\).
• Tạo một cạnh nối từ \(start_{r_1, c_1}\) đến \(end_{r_2, c_2}\) nếu có cách chọn hướng của băng chuyền trong ô \((r_1, c_1)\) sao cho con lemming kết thúc ở \((r_2, c_2)\) sau một giây.

Tất cả các nút \(start\) sẽ có đúng hai cạnh kề vì có đúng hai ô khác nhau mà một con lemming có thể kết thúc trong một giây bắt đầu từ bất kỳ ô nào cho trước. Mặt khác, các nút \(end\) có thể có từ \(0\) đến \(8\) cạnh kề, tùy thuộc vào định hướng băng chuyền của các ô lân cận.

Hãy quan sát đồ thị thêm một chút. Có hai quy tắc được áp dụng:

1. Nếu không có cạnh nào kề với một nút \(end_{r, c}\), thì không con lemming nào có thể kết thúc ở ô \((r, c)\) trong một giây, vì vậy sẽ có hai con lemming ở một ô khác nào đó bất kể chúng ta định hướng băng chuyền như thế nào. Trong trường hợp đó, câu trả lời đơn giản là \(0\).
2. Nếu có một nút \(end_{r_2, c_2}\) chỉ kề với một cạnh dẫn đến \(start_{r_1, c_1}\), thì chúng ta không có lựa chọn nào khác ngoài việc định hướng băng chuyền trên ô \((r_1, c_1)\) dẫn đến ô \((r_2, c_2)\). Sau đó, chúng ta có thể đơn giản loại bỏ cả \(end_{r_2, c_2}\) và \(start_{r_1, c_1}\) khỏi đồ thị cùng với tất cả các cạnh kề.

Chúng ta có thể áp dụng các quy tắc này lặp đi lặp lại cho đến khi không thể áp dụng được nữa.

Gọi \(N\) là số nút \(start\) còn lại sau khi quá trình trên hoàn tất. Số lượng nút \(end\) cũng bằng \(N\), vì chúng ta đã loại bỏ chúng theo cặp.

Số lượng cạnh kề với mỗi nút \(start\) vẫn bằng hai, vì vậy tổng số cạnh bằng \(2 \cdot N\) vì đồ thị là đồ thị hai phía. Chúng ta cũng biết rằng mỗi nút \(end\) hiện tại kề với ít nhất hai cạnh, vì các quy tắc trên không còn áp dụng được nữa.

Nhưng, nếu bất kỳ nút \(end\) nào có nhiều hơn hai cạnh kề, thì tổng số cạnh kề với tất cả các nút \(end\) cộng lại sẽ lớn hơn \(2 \cdot N\). Điều này sẽ mâu thuẫn với thực tế là tổng số cạnh bằng \(2 \cdot N\). Do đó, số lượng cạnh kề với mỗi nút \(end\) cũng bằng đúng hai.

Bất kỳ đồ thị nào có tất cả các bậc của nút bằng hai thực chất là một tập hợp các chu trình. Đối với đồ thị hai phía, độ dài của mỗi chu trình là chẵn. Vì vậy, chúng ta còn lại \(K\) chu trình có độ dài chẵn mà chúng ta có thể giải quyết độc lập và nhân các kết quả riêng lẻ để có con số cuối cùng.

Để giải quyết một chu trình, hãy chọn bất kỳ ô \((r_1, c_1)\) nào và chọn một hướng băng chuyền. Con lemming kết thúc ở \((r_2, c_2)\). Bây giờ loại bỏ \(start_{r_1, c_1}\) và \(end_{r_2, c_2}\) khỏi đồ thị cùng với các cạnh kề. Điều này sẽ phá vỡ chu trình, và chúng ta có thể tiếp tục áp dụng quy tắc số 2 cho đến khi quyết định được băng chuyền cho tất cả các ô còn lại. Bởi vì chu trình có độ dài chẵn và chúng ta luôn loại bỏ các nút theo cặp, quy tắc số 1 sẽ không bao giờ xảy ra.

Chúng ta có thể chọn hướng của ô \((r_1, c_1)\) theo hai cách. Vì vậy, câu trả lời cho bất kỳ chu trình nào luôn là \(2\). Do đó, câu trả lời cuối cùng bằng \(2^K \pmod{1000003}\).

Độ phức tạp

Xây dựng đồ thị mất \(O(R \cdot C)\). Quá trình loại bỏ các nút bậc 1 có thể thực hiện bằng hàng đợi (tương tự như tìm các thành phần không phải là lá của đồ thị) trong \(O(R \cdot C)\). Đếm số chu trình cũng mất \(O(R \cdot C)\). Tổng độ phức tạp là \(O(R \cdot C)\) cho mỗi bộ test.

Dựa trên phân tích chính thức của Google Code Jam.