Subtask 1

Quay lui, thử mọi tổ hợp xếp quân vua.

Độ phức tạp: \(O(2^{N^2})\).

Subtask 2,3

Sử dụng quy hoạch động và mặt nạ bit AKA bitmask. Thay vì quy hoạch động 2 chiều theo bàn cờ, hay gì đó tương tự, thì ta sẽ xem xét các hàng xếp quân vua theo dãy nhị phân, với 1 là xếp vua và 0 là không. Ví dụ:

000010100

Thì ta có thể đặt một dãy bit khác sao cho không con vua nào tấn công nhau, ví dụ:

000010100
101000001

Đầu tiên ta quay lui và nhét tất cả các dãy bit thỏa mãn (không con vua nào trên dãy đó ăn nhau) vào một vector hay mảng, gọi mask số lượng dãy bit đó.

Xét dp[i][j][k] với \(i\) là hàng thứ \(i\), \(j\) là dãy bit thứ \(j\) sẽ được sử dụng, và \(k\) là tổng số quân vua được sử dụng. Ta có công thức truy hồi như sau:

for(int i=2;i<=n;++i)
for(int j=0;j<m;++j)
for(p=0;p<=k;++p) {
if(p<cnt[j]) continue;
pp=p-cnt[j];
for(u=0;u<m;++u)
if(check(gay[j],gay[u])) dp[i][j][p]+=dp[i-1][u][pp];
}

Ý tưởng nói chung là với dãy bit thứ \(j\), ta sẽ xem xem có bao nhiêu cách đạt được trạng thái này với \(k\) con vua. Số cách đạt được trạng thái dp[i][j][k] chính là bằng tổng số cách đạt được các trạng thái dp[i-1][u][k - số bit 1 của dãy thứ j] với \(u\) là dãy bit thứ \(u\) của hàng \(i-1\) mà không xung đột với dãy thứ \(j\) của hàng \(i\).

Kết quả sẽ là tổng dp[N][i][K] với \(i \in [1..mask]\).

Độ phức tạp là \(O(N \times M^2 \times K)\) với \(N\) là số hàng của bàn cờ, \(M\) là số bitmask, \(K\) là số lượng quân vua.