Editorial for bwtile: Tô màu 3

Hiểu bài toán

Bài toán yêu cầu đếm số cách tô màu một bảng m x n gồm các ô vuông với 2 màu đen và trắng sao cho:

1. Có chính xác k ô được tô màu đen.
2. Hai ô liền kề nhau (chung cạnh) không được tô cùng màu.

Điều kiện 2 là một ràng buộc rất mạnh. Nó buộc bảng phải được tô theo một kiểu 'bàn cờ' (checkerboard). Nếu chọn màu cho ô (1,1) thì màu của tất cả các ô khác sẽ được xác định duy nhất.

Giả sử ô (1,1) được tô màu Trắng:

• Các ô có t tổng chỉ số hàng và cột (i+j) chẵn sẽ là Trắng.
• Các ô có tổng i+j lẻ sẽ là Đen.

Giả sử ô (1,1) được tô màu Đen:

• Các ô có tổng i+j chẵn sẽ là Đen.
• Các ô có tổng i+j lẻ sẽ là Trắng.

Như vậy, có tối đa 2 cách tô màu thỏa mãn ràng buộc chung cạnh (tương ứng với 2 màu của ô (1,1)). Tuy nhiên, mỗi cách tô này sẽ có số lượng ô màu đen cố định:

• Gọi số ô có tổng chỉ số chẵn là A.
• Gọi số ô có tổng chỉ số lẻ là B.

Ta có:

• Nếu m * n là số chẵn thì A = B = (m * n) / 2.
• Nếu m * n là số lẻ thì A = (m * n + 1) / 2 và B = (m * n - 1) / 2 (tùy vào việc ô (1,1) được tính vào nhóm nào).

Bài toán quy về đếm xem có bao nhiêu trong 2 cách tô trên có đúng k ô màu đen.

• Nếu m*n chẵn: Mỗi cách tô cho A ô đen. Nếu k = A thì có 2 cách, ngược lại 0 cách.
• Nếu m*n lẻ: Cách tô 1 cho A ô đen, cách tô 2 cho B ô đen. Nếu k = A hoặc k = B thì có 1 cách (tương ứng), ngược lại 0 cách.

Các cách tiếp cận

Cách Phân tích số học (Mathematical Analysis)

#include <iostream>
using namespace std;

int main() {
    long long m, n, k;
    cin >> m >> n >> k;

    long long total = m * n;
    long long even_cells = (total + 1) / 2; // Số ô có (i+j) chẵn
    long long odd_cells = total / 2;        // Số ô có (i+j) lẻ

    long long ans = 0;

    // Nếu k bằng số ô ở vị trí chẵn, tăng ans lên 1
    if (k == even_cells) ans++;
    // Nếu k bằng số ô ở vị trí lẻ, tăng ans lên 1
    if (k == odd_cells) ans++;

    cout << ans;
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Phương pháp này dựa trên nhận định rằng bảng chỉ có thể được tô theo đúng 2 kiểu 'bàn cờ' (tương ứng màu ô (1,1) là Trắng hoặc Đen).

1. Tính tổng số ô: total = m * n.
2. Tính số ô nằm ở các vị trí có tổng chỉ số hàng+cột chẵn: even_cells = (total + 1) / 2. Kỹ thuật này dùng số nguyên chia để lấy kết quả chính xác cho cả trường hợp total chẵn và lẻ.
3. Tính số ô nằm ở các vị trí có tổng chỉ số hàng+cột lẻ: odd_cells = total / 2.
4. So sánh k với even_cells và odd_cells:
   • Nếu k == even_cells: Có 1 cách tô (ô (1,1) màu Đen).
   • Nếu k == odd_cells: Có 1 cách tô (ô (1,1) màu Trắng).
   • Nếu k bằng cả hai (chỉ xảy ra khi total chẵn và even_cells == odd_cells): Có 2 cách.
   • Nếu k không bằng bằng bất số nào: 0 cách.
5. In ra kết quả.

Cách Phân loại theo tính chẵn lẻ của bảng

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long m, n, k;
    cin >> m >> n >> k;
    long long total = m * n;
    long long A = (total + 1) / 2;
    long long B = total / 2;

    if (A == B) { // Khi tổng số ô là số chẵn
        if (k == A) cout << 2;
        else cout << 0;
    } else { // Khi tổng số ô là số lẻ
        if (k == A || k == B) cout << 1;
        else cout << 0;
    }
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Cách tiếp cận này chia vấn đề làm 2 trường hợp chính dựa trên t tổng số ô:

1. Bảng có t tổng số ô chẵn (m * n % 2 == 0):

   • Khi đó số ô vị trí chẵn bằng số ô vị trí lẻ (A == B).
   • Nếu muốn có k ô đen, k必须等于 A. Vì có 2 cách tô (ô (1,1) Trắng hoặc Đen) đều cho ra số ô đen là A.
   • Kết quả: 2 nếu k == A, ngược lại 0.

2. Bảng có tổng số ô lẻ (m * n % 2 != 0):

   • Khi đó số ô vị trí chẵn nhiều hơn 1 hoặc ít hơn 1 so với vị trí lẻ (A != B).
   • Nếu k == A, chỉ có 1 cách tô (ô (1,1) thuộc nhóm có số lượng nhiều hơn).
   • Nếu k == B, chỉ có 1 cách tô (ô (1,1) thuộc nhóm có số lượng ít hơn).
   • Các giá trị k khác đều không thể.
   • Kết quả: 1 nếu k == A hoặc k == B, ngược lại 0.

Cách này logic rõ ràng, dễ theo dõi.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Ràng buộc 'không ô chung cạnh cùng màu' buộc bảng phải được tô theo đúng 2 kiểu 'bàn cờ' (checkerboard pattern) duy nhất.
• Vấn đề chỉ còn lại là đếm xem trong 2 kiểu tô đó, có bao nhiêu kiểu cho ra đúng k ô màu đen.
• Số ô màu đen trong mỗi kiểu tô phụ thuộc hoàn toàn vào t tổng số ô và sự chẵn lẻ của nó.

Lỗi thường gặp

• Sử dụng kiểu dữ liệu nhỏ (int) gây tràn số khi m và n lên tới 10^9 (tổng có thể lên tới 10^18). Cần dùng long long (C++) hoặc long (Java).
• Việc tính toán số ô chẵn/lẻ cần chính xác. Ví dụ: (m*n + 1) / 2 là công thức chuẩn để lấy số nguyên lớn hơn hoặc bằng một nửa tổng.
• Quên kiểm tra trường hợp k quá lớn hoặc âm (dù đề bài giới hạn k >= 0, nhưng k có thể lớn hơn m*n).