Subtask 1, 3

Các bạn chỉ cần cày trâu từng cặp bàn cờ là xong.

Độ phức tạp: ~O\left(\dfrac{n(n + 1)}{2} \times k^2 \times 4\right)~.

Note: Máy chấm TLEOJ rất khỏe, sẽ không đời nào TLE đâu, trừ khi máy chấm bị gì gì đó hoặc code sai. Nhưng máy chấm TomChienXuOJ thì ếu :))

Subtask 2

Ý tưởng được đặt ra là ta có thể nén bàn cờ thành số dưới dạng unsigned long long trên C++. Từ đó ta có thể so sánh số thay vì so sánh cả bảng.

Độ phức tạp: ~O\left(\dfrac{n(n + 1)}{2} \times 4\right)~

• Cải tiến #1: Giả sử 2 bàn cờ xoay thành tương ứng ra ~a_1, a_2, a_3, a_4~ và ~b_1, b_2, b_3, b_4~. Nếu hai bàn cờ bằng nhau thì với mọi cách xoay của ~a~ luôn tìm ra cách xoay ~b~ thỏa mãn. Ta có thể thay vì lấy cả bốn cách xoay thì chỉ cần lấy một giá trị ~\min~ hoặc ~\max~. Độ phức tạp chia ~4~, còn lại ~O\left(\dfrac{n(n + 1)}{2}\right).~
• Cải tiến #2: Ta có thể đếm phân phối. Độ phức tạp chia ~4~ còn lại ~O\left(n \times \log{n}\right)~.

Subtask 4

Từ subtask 2, ta có thể nghĩ đến hash. Chú ý người ra đề có thể diệt các mod quen thuộc như ~10^9 + 7; 10^9 + 9; 998244353~. Bạn có thể dùng mod lớn hơn hoặc dùng nhiều mod (ví dụ ba mod cùng lúc).

Dựa vào idea Cải tiến #1, ta được độ phức tạp ~O\left(\dfrac{n(n + 1)}{2}\right)~.

Subtask 5

Vẫn là subtask 4 nhưng dựa vào Cải tiến #2, ta có độ phức tạp ~O\left(n \times \log{n}\right)~.