Trước tiên, ta nghĩ một thuật toán quy hoạch động đơn giản cho bài này. Nhận thấy $m$ nhỏ
nên ta nghĩ ngay đến quy hoạch động bitmask: gọi $f[i][mask_1][mask_2]$ là số cách điền
bảng $i\times m$, với cột thứ $i-1$ và cột $i$ lần lượt được xếp các quân mã theo cấu hình
$mask_1$ và $mask_2$. Cách chuyển trạng thái khá đơn giản:
$f[i][mask_1][mask_2]=\sum_{mask_3} f[i-1][mask_2][mask_3]$
Thỏa mãn các cấu hình $mask_1,mask_2,mask_3$ đôi một không mâu thuẫn (mâu thuẫn tức là có
hai con mã tấn công nhau).
Tới đây ta nhận thấy bản chất công thức truy hồi này vẫn là một công thức truy hồi tuyến
tính, từ đó có thể thử áp dụng ngay nhân ma trận để giải. Tuy nhiên, điều này đồng nghĩa
với việc ta cần một ma trận vuông kích thước $2\times 2^{2m}=512$ khi $m=4$, nên việc nhân
ma trận một lần cũng đã đủ lâu, chưa kể việc ta nhân nó $\log n$ lần.
Để tối ưu thì ta nhận thấy khi tính $f[i][mask_1][mask_2]$, ta không cần quan tâm tới các bộ
$(mask_1,mask_2)$ bị mâu thuẫn, vì giá trị của nó chắc chắn bằng $0$ rồi. Nếu thử code sinh
hết các bộ không mâu thuẫn thì khi $m=4$, chỉ có $81$ bộ thỏa mãn! Khi này, ta chỉ cho vào
ma trận các bộ thỏa mãn để tính, nên bây giờ ma trận chỉ có kích thước $162\times162$, đủ
tốt để có thể nhân ma trận $\log n$ lần.
Code mẫu:
```cpp
#include <bits/stdc++.h>
using ll = long long;
#define all(a) a.begin(), a.end()
#define SZ(a) (int)(a).size()
using namespace std;
const int mod = 1e9 + 7;
void solve(){
int n, m;
cin >> n >> m;
auto valid = [&](int m1, int m2){
for (int i = 0; i < m; ++i){
int j = (i + 2 < m) ? i + 2 : i - 2;
if ((m1 >> i & 1) && (m2 >> j & 1)) return false;
}
return true;
};
using mat = vector<vector<int>>;
mat id(1 << m, vector<int>(1 << m, -1));
int k = 0;
for (int m1 = 0; m1 < (1 << m); ++m1){
for (int m2 = 0; m2 < (1 << m); ++m2)
if (valid(m1, m2)) id[m1][m2] = k++;
}
auto mul = [](mat a, mat b){
mat c(SZ(a), vector<int>(SZ(b[0]), 0));
int n = SZ(b);
for (int i = 0; i < SZ(a); ++i){
for (int j = 0; j < SZ(b[0]); ++j){
for (int k = 0; k < n; ++k){
ll s = 1ll * a[i][k] * b[k][j] % mod;
c[i][j] += s;
if (c[i][j] >= mod) c[i][j] -= mod;
}
}
}
return c;
};
mat coef(2 * k, vector<int>(2 * k));
for (int i = 0; i < k; ++i)
coef[k + i][i] = 1;
// tính base matrix (chứa dp[3] và dp[2])
int dp[4][16][16]; memset(dp, 0, sizeof dp);
for (int mask = 0; mask < (1 << m); ++mask)
dp[1][mask][0] = 1;
for (int i = 2; i <= 3; ++i){
for (int m1 = 0; m1 < (1 << m); ++m1){
for (int m2 = 0; m2 < (1 << m); ++m2){
for (int m3 = 0; m3 < (1 << m); ++m3){
if (id[m1][m2] == -1 || id[m2][m3] == -1) continue;
bool flag = true;
for (int i = 0; i < m; ++i){
if (i - 1 >= 0)
if ((m1 >> i & 1) && (m3 >> (i - 1) & 1)) flag = false;
if (i + 1 < m)
if ((m1 >> i & 1) && (m3 >> (i + 1) & 1)) flag = false;
}
if (flag){
coef[id[m1][m2]][id[m2][m3]] = 1;
dp[i][m1][m2] += dp[i - 1][m2][m3];
if (dp[i][m1][m2] >= mod) dp[i][m1][m2] -= mod;
}
}
}
}
}
if (n <= 3){
int res = 0;
for (int m1 = 0; m1 < (1 << m); ++m1){
for (int m2 = 0; m2 < (1 << m); ++m2){
res += dp[n][m1][m2];
if (res >= mod) res -= mod;
}
}
cout << res;
return;
}
mat base;
for (int i = 3; i >= 2; --i){
for (int m1 = 0; m1 < (1 << m); ++m1){
for (int m2 = 0; m2 < (1 << m); ++m2){
if (id[m1][m2] == -1) continue;
base.push_back({dp[i][m1][m2]});
}
}
}
mat res(2 * k, vector<int>(2 * k));
for (int i = 0; i < 2 * k; ++i)
res[i][i] = 1;
for (int p = n - 3; p; p >>= 1, coef = mul(coef, coef))
if (p & 1) res = mul(res, coef);
res = mul(res, base);
int ans = 0;
for (int i = 0; i < k; ++i){
ans += res[i][0];
if (ans >= mod) ans -= mod;
}
cout << ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}
```
tuongll
Created at
0 likes