Tổng quan

Bài toán này khá khó, tuy nhiên nếu các bạn quyết tâm thì vẫn có thể làm được vài subtask đơn giản, hoặc giải được 1 trường hợp (được tầm \(50/100\)). Tuy nhiên rất tiếc chỉ có một bạn có điểm số dương cho bài này :(.

Lời giải

Đầu tiên, để ý rằng số con vua bị chiếu tối đa chỉ có thể là \(8\). Đồng thời với mỗi hướng bị chiếu, chúng ta có thể tính được có bao nhiêu ô nằm trên hướng đó. Gọi số hướng là \(x (x \leq 8)\) và số ô mỗi hướng là \(a_1,a_2,...,a_x\).

• **Trường hợp 1: ** \(k \leq x\)

Trường hợp này số con vua tối đa là \(k\). Đồng thời, mỗi hướng có tối đa \(1\) con vua, và mỗi con vua bắt buộc phải nằm trên \(1\) hướng nào đó. Đầu tiên chúng ta sẽ chọn ra một tập \(k\) hướng để đặt vua. Giả sử \(k = 3\) và ta chọn các hướng \(\{1, 2, 3\}\), số cách đặt vua sẽ là \(a_1a_2a_3\) theo quy tắc nhân.

Chúng ta cần liệt kê tất cả bộ \(k\) hướng từ \(x\) hướng. Điều này có thể thực hiện bằng cách liệt kê tất cả tập con của \(\{1, 2, ..., x\}\) và chọn các tập con có số phần tử là \(k\).

Độ phức tạp: \(O(2^x)\)

• **Trường hợp 2: ** \(k > x\)

Trường hợp này số con vua tối đa sẽ là \(x\). Bài toán quy về: Đặt \(k\) con vua lên bàn cờ sao cho mỗi hướng phải chứa ít nhất một con vua. Để giải quyết, chúng ta sẽ dùng công thức bao hàm loại trừ:

• Số cách đặt tổng cộng là \(C_{mn-1}^{k}\)

• Số cách đặt mà hướng \(i\) không có vua là \(C_{mn - 1 - a_i}^{k}\)

• Số cách đặt mà hướng \(i\) và \(j\) không có vua là \(C_{mn - 1 - a_i - a_j}^{k}\)

• ...

Như vậy chúng ta sẽ liệt kê tất cả tập con của \(\{1, 2, ..., x\}\), áp dụng cách tính trên, rồi cộng hoặc trừ vào đáp số dựa trên tính chẵn lẻ của số phần tử (cộng nếu số phần tử là chẵn, trừ nếu lẻ).

Chẳng hạn nếu \(x = 3\) thì đáp số của chúng ta sẽ là: \(\(C_{mn-1}^{k} - C_{mn - 1 - a_1}^{k} - C_{mn - 1 - a_2}^{k} - C_{mn - 1 - a_3}^{k} + C_{mn - 1 - a_1 - a_2}^{k} + C_{mn - 1 - a_1 - a_3}^{k} + C_{mn - 1 - a_2 - a_3}^{k} - C_{mn - 1 - a_1 - a_2 - a_3}^{k}\)\)

Độ phức tạp: \(O(2^x)\)