Tóm tắt đề bài: Cho một bảng gồm ~N~ hàng và ~M~ cột. Có ~K~ ô bị đánh dấu trong bảng. Hãy đếm cách xếp các viên gạch kích thước ~1 \times 2~ hoặc ~2 \times 1~ sao cho các viên gạch xếp kín bảng, và không nằm đè lên các ô cấm.

Bạn đọc nên tìm hiểu trước về quy hoạch động bitmask.

Nhận xét: Điều kiện ~N \le 10~ khá "lạ", ta nghĩ đến trạng thái quy hoạch động: ~dp[i][j]~ là số cách xếp đến hết hàng ~i~ và trạng thái cột ~i~ là ~mask~.

Ta có thể chuyển trạng thái dễ dàng.

Độ phức tạp: ~O~ (~2^N \times M~).