Tóm tắt đề bài: Cho bảng kích thước ~N \times M~, và ~K~ ô có chữ ~X~. Hãy đếm số lượng hình chữ nhật con có ít nhất một chữ ~X~.

Subtask 1: ~K = 1~.

Ở subtask này, vì chỉ có một chữ ~X~, ta cần tìm số hình chữ nhật con chứa ô ~(x_1, y_1)~.

Dễ thấy: Một hình chữ nhật con có ô trên trái ~(x, y)~ và ô dưới phải ~(u, v)~ sẽ thỏa mãn nếu: ~x \le x_1 \le u~ và ~y \le y_1 \le v~.

Vì vậy, chọn ra ~x~ có ~x_1~ cách chọn, chọn ra ~y~ có ~y_1~ cách chọn, chọn ra ~u~ có ~n - x_1 + 1~ cách chọn, chọn ra ~v~ có ~m - y_1 + 1~ cách chọn. Ta nhân các số này lại và nhận được kết quả.

Độ phức tạp: ~O~ (~1~).

Subtask 2: ~K = 2~.

Vẽ sơ đồ Venn, ta thấy: kết quả là số lượng hình chữ nhật phủ một chữ ~X~ thứ nhất và thứ hai, trừ đi số lượng hình chữ nhật phủ cả hai chữ ~X~.

Độ phức tạp: ~O~ (~1~).

Subtask 3: ~K \le 20~.

Mở rộng subtask 2, xuất phát từ ý tưởng bao hàm loại trừ, kết quả sẽ là: số lượng hình chữ nhật phủ ít nhất ~1~ chữ ~X~, trừ đi số lượng hình chữ nhật phủ ít nhất ~2~ chữ ~X~, cộng thêm số lượng hình chữ nhật phủ ít nhất ~3~ chữ ~X~, ...

Độ phức tạp: ~O~ (~2^K~).