Bài gợi ý: CSES - Grid Completion | Hoàn Thành Bảng Số

Tóm tắt: Cho một bảng vuông kích thước \(N \times N\), trên đó một số ô đã điền sẵn chữ A hoặc chữ B. Bạn cần điền thêm vào các ô trống sao cho mỗi hàng và mỗi cột đều có đúng một chữ A và đúng một chữ B, đồng thời không ô nào chứa cả hai chữ. Hãy đếm số cách hoàn thành bảng theo modulo \(10^9 + 7\).

Ta xét một ví dụ nhỏ với \(N = 3\). Giả sử ban đầu ô \((1, 1)\) có chữ A và ô \((2, 2)\) có chữ B. Việc đặt chữ A vào mỗi hàng thực chất là chọn một hoán vị cột \(p\) sao cho \(p_1 = 1\). Đặt chữ B là chọn hoán vị cột \(q\) với \(q_2 = 2\). Điều kiện không ô nào chứa cả hai chữ đồng nghĩa với việc \(p_i \neq q_i\) ở tất cả các hàng \(i = 1, 2, 3\).

Nếu thử chọn từng vị trí rồi kiểm tra xem có ô nào bị trùng không, ta sẽ gặp bế tắc vì các ràng buộc hàng và cột đan xen phức tạp. Với \(N \le 500\), số cách điền tự do có thể lên tới \(500!\), nên không thể thử từng trường hợp. Vậy làm sao để xử lý điều kiện "không có hàng nào bị trùng \(p_i = q_i\)"?

Khi gặp điều kiện "mọi phần tử đều không được vi phạm", hướng đi tự nhiên là dùng nguyên lý bù trừ (inclusion-exclusion). Thay vì chỉ đếm các cách hợp lệ, ta chủ động chọn ra một số hàng cố tình để vi phạm, tức là ép \(p_i = q_i\). Sau khi đã cố định các vị trí vi phạm, các hàng và cột còn lại được ghép tự do bằng các giai thừa.

Để đếm số cách chọn các cặp vi phạm, ta phân loại các hàng và cột thành các nhóm: nhóm chỉ có A, nhóm chỉ có B, và nhóm trống cả hai. Ta dùng quy hoạch động (DP - phương pháp lưu lại kết quả bài toán con để tính bài toán lớn hơn) với mảng dp[i][j] là số cách chọn \(j\) vị trí trùng từ \(i\) hàng trống hoàn toàn. Ở mỗi bước, ta xét hàng thứ \(i\): hoặc không ép trùng, hoặc ghép nó trùng với một trong các cột còn trống.

Khi cài đặt, bạn có thể chia thành các bước rõ ràng:

• Phân loại và đếm số lượng hàng, cột thuộc từng nhóm trạng thái.
• Tính trước mảng giai thừa và tổ hợp theo modulo \(10^9 + 7\).
• Dùng quy hoạch động để đếm số cách tạo ra các điểm trùng nhau giữa A và B.
• Áp dụng công thức bù trừ với dấu \((-1)^k\) nhân với số cách điền tự do của các phần tử còn lại.

Bài tập tương tự:

• Hoán vị không bất động (THTC Vòng Khu vực 2021): Rèn luyện tư duy bù trừ trên bài toán đếm hoán vị không có điểm cố định.
• Giao bài tập: Luyện tập kỹ thuật kết hợp quy hoạch động và bù trừ khi có nhiều điều kiện ràng buộc.

Duyệt số lượng vị trí vi phạm \(k\) từ \(0\) đến \(N\), nhân hệ số đan dấu với số cách điền các vị trí tự do còn lại, rồi cộng dồn vào đáp án theo modulo \(10^9 + 7\).