Subtask 1,2

Vì giới hạn nhỏ nên ta có thể áp dụng đệ quy quay lui. Chú ý subtask 2 các bạn cần cải tiến thêm để có thể được full điểm

Subtask 3, 4

Giới hạn $n$ nhỏ làm ta nghĩ đến dp-bitmask. Các bạn có thể đọc tại đây

Ý tưởng: Gọi $dp[i][j]$ là số cách để xếp vua trong ma trận $n\cdot j$, với những con vua được đặt trong hàng $j$ tương ứng với mask $i$

Công thức: $dp[i][j]=\displaystyle \sum_{mask \, = \, 0}^{2^n-1} dp[mask][j-1]\cdot check(mask,i)$

Trong đó hàm $check(mask,i)$ để kiểm tra xem nếu 2 hàng bàn cờ có hàng 1 mô phỏng các con vua tương ứng với giá trị $mask$ và hàng 2 tương ứng với giá trị $i$ thì trong 2 hàng đó không có con vua nào tấn công nhau