Bài này chúng ta có thể biểu diễn 1 hàng cờ bằng mask và gọi bài toán như sau:

• Định nghĩa bit 1 là vị trí đặt quân mã, 0 là vị trí trống (chỉ cần quan tâm đến quân mã không cần quan tâm đến bất kì quân cờ nào khác).

• dp[i][mask][pre] là hàng thứ i cấu hình mask và hàng thứ i - 1 cấu hình pre.

• Có thể nhận thấy rằng 1 con mã hàng i có thể tấn công tới hàng i - 3 vì thế ta chỉ cần quan tâm đến 4 mask của các hàng i, i-1, i-2, i-3.

• Bài toán sẽ được chia làm 2 bước:

  • Kiểm tra các cấu hình:

    • Kiểm tra 2 cấu hình

    • Kiểm tra 3 cấu hình

    • Lưu ý cần quan tấm đến các bit kề nếu bit hiện tại đang là vị trí đặt mã (vì sao bạn có thể đọc qua luật cờ tướng :3)

  • Cách thức:

    • Sau khi có xây dựng xong các hàm kiểu tra 2 cấu hình, 3 cấu hình có thể lưu lại mảng để giảm thời gian chạy

    • Ta có thể thấy bài toán bắt đầu phức tạp khi m >= 4 các trường hợp còn lại có thể chạy chay để lưu đáp án

    • Với mỗi hàng i như đã nói ta cần quan tâm đến 4 cấu hình của nó và theo cách gọi bài toán có được công thức truy hồi

Độ phức tạp sấp sĩ O(m x 2^4n)

Dưới đây là phần code tham khảo của mình:

#include <bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define pii pair<int, int>
#define fi first
#define se second
#define gcd __gcd
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define inf32 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
#define forr(i, a, b) for (int i = a; i <= b; i++)
#define fodd(i, a, b) for (int i = a; i >= b; i--)
#define bit(n, i) ((n >> i) & 1)
#define el '\n'
#define TASK "test"
using namespace std;


const int d4x[4] = {-1, 0, 1, 0};
const int d4y[4] = {0, 1, 0, -1};
const ll mode = 1e9 + 7;
const int N = 1e2 + 3;


ll n, m, dp[N][1 << 6][1 << 6];
bool ok[1 << 6][1 << 6], check[1 << 6][1 << 6][1 << 6];


bool oke (int mask, int pre){
    for (int i = 0; i < n - 2; i++){
        if (bit(mask, i) == 0) continue;
        if (bit(mask, i + 1)){
if (bit(pre, i + 2) && bit(pre, i + 1) == 0) return false;
        }
        else{
if (bit(pre, i + 2)) return false;
        }
    }
    for (int i = 0; i < n - 2; i++){
        if (bit(pre, i) == 0) continue;
        if (bit(pre, i + 1)){
if (bit(mask, i + 2) && bit(mask, i + 1) == 0) return false;
        }
        else{
if (bit(mask, i + 2)) return false;
        }
    }
    return true;
}


bool checks(int mask, int pre, int pre_mask){
    for (int i = 0; i < n - 1; i++){
        if (bit(mask, i) == 0) continue;
        if (bit(pre, i)){
if (bit(pre_mask, i + 1) && bit(pre, i + 1) == 0) return false;
        }
        else{
if (bit(pre_mask, i + 1)) return false;
        }
    }
    for (int i = 0; i < n - 1; i++){
        if (bit(pre_mask, i) == 0) continue;
        if (bit(pre, i)){
if (bit(mask, i + 1) && bit(pre, i + 1) == 0) return false;
        }
        else{
if (bit(mask, i + 1)) return false;
        }
    }
    return true;
}


void solve() {
    cin >> n >> m;
    if (m == 1){
        cout << (1 << n);
        return;
    }
    memset(ok, false, sizeof ok);
    memset(check, false, sizeof check);
    for (int mask = 0; mask < (1 << n); mask++){
        for (int pre = 0; pre < (1 << n); pre++){
if (oke(mask, pre)){
    ok[mask][pre] = true;
    dp[2][mask][pre]++;
}
        }
    }
    for (int mask = 0; mask < (1 << n); mask++){
        for (int pre = 0; pre < (1 << n); pre++){
                    if (!ok[mask][pre]) continue;
for (int pre_mask = 0; pre_mask < (1 << n); pre_mask++){
    if (!ok[pre][pre_mask]) continue;
    if (!checks(mask, pre, pre_mask)) continue;
    check[mask][pre][pre_mask] = true;
    dp[3][mask][pre]++;
}
        }
    }
    for (int i = 4; i <= m; i++){
        /// tang 1
        for (int mask = 0; mask < (1 << n); mask++){
                    /// tang 2
for (int pre = 0; pre < (1 << n); pre++){
    if (!ok[mask][pre]) continue;
    /// tang 3
    for (int pre_mask = 0; pre_mask < (1 << n); pre_mask++){
        if (!ok[pre][pre_mask]) continue;
        if (!check[mask][pre][pre_mask]) continue;
        /// tang 4
        for (int dia_nguc = 0; dia_nguc < (1 << n); dia_nguc++){
            if (!ok[pre_mask][dia_nguc]) continue;
            if (!check[pre][pre_mask][dia_nguc]) continue;
            dp[i][mask][pre] += dp[i - 2][pre_mask][dia_nguc];
            dp[i][mask][pre] %= mode;
        }
    }
}
        }
    }
    int ans = 0;
    for (int mask = 0; mask < (1 << n); mask++){
        for (int pre = 0; pre < (1 << n); pre++){
ans = (ans + dp[m][mask][pre]) % mode;
        }
    }
    cout << ans;
}


void file() {
    if (fopen(TASK ".inp", "r")) {
        freopen(TASK ".inp", "r", stdin);
        freopen(TASK ".out", "w", stdout);
    }
}


signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    file();
    solve();
}