### 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:
````cpp
#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();
}
lam280407
Created at
4 likes