洛谷P5005 中国象棋 - 摆上马 题解
题目链接:P5005 中国象棋 - 摆上马
题意:
cxy 有一个 \(X\) 行 \(Y\) 列的棋盘,还有很多完全相同的马(你可以认为有无数个)。现在在棋盘上摆上马(或者不摆),求任何马无法攻击另一匹马的方案总数。
中国象棋的马和国际象棋的马不同。
注意:实际问题中是没有兵的。
当然由于方案可能过多,请输出对 \((10^9+7)\) 取模的值。
输入格式:
第一行两个正整数 \(X,Y\)。
输出格式:
方案对 \((10^9+7)\) 取模的值。
数据范围:
对于 100% 的数据,有 \(1\le X\leq100\),\(1\le Y\leq6\)。
设 \(f(i,j,k)\) 表示考虑前 \(i\) 行,当前行的状态为 \(j\) ,上一行的状态为 \(k\) 时的方案数,则 ( \(\uparrow\) 表示 +=
) \[
f_{i,j,k} \uparrow f_{i-1,k,l}
\] 这个转移方程很容易得出,但是它的前提是 \((j,k),(s,k),(s,j)\)
均不冲突。判断的代码如下:
int atk1(int a) // 判断里层
{
int c = 0;
for(int i = 1; bit(-1, i) <= a; i++)
{
if(!check(a, i)) continue;
if(!check(a, i) || !check(a, i - 1)) c |= bit(-1, i - 2);
if(!check(a, i) || !check(a, i + 1)) c |= bit(-1, i + 2);
}
return c;
}
int atk2(int a,int b) // 判断外层
{
int c = 0;
for(int i = 1; bit(-1, i) <= a; i++)
{
if(!check(a, i)) continue;
if(!check(a, i) || !check(b, i)) c |= (bit(-1, i - 1) | bit(-1, i + 1));
}
return c;
}
这里的里层表示横着跳的那种。
然后你交上去发现 MLE 了。看了一眼空间限制,啊,居然是 1MB ,所以要滚动数组。
时间复杂度 \(\mathcal{O}(R\times 2^{2C})\)
代码:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)((1 << 6) + 2))
int f[3][N][N]; const int mod = 1e9 + 7;
void add(int &x,int y) { (x += y) >= mod ? x -= mod : 0; }
int bit(int a,int x) {
if(x < 1) return 0; else return (a & (1 << (x - 1)));
}
bool check(int a,int x) {
if(x < 1) return false; else return (a & (1 << (x - 1)));
}
int atk1(int a)
{
int c = 0;
for(int i = 1; bit(-1, i) <= a; i++)
{
if(!check(a, i)) continue;
if(!check(a, i) || !check(a, i - 1)) c |= bit(-1, i - 2);
if(!check(a, i) || !check(a, i + 1)) c |= bit(-1, i + 2);
}
return c;
}
int atk2(int a,int b)
{
int c = 0;
for(int i = 1; bit(-1, i) <= a; i++)
{
if(!check(a, i)) continue;
if(!check(a, i) || !check(b, i)) c |= (bit(-1, i - 1) | bit(-1, i + 1));
}
return c;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int R,C; cin >> R >> C; const int mx = (1ll << C);
for(int i = 0; i < mx; i++) f[1][i][0] = 1;
for(int i = 0; i < mx; i++) {
for(int j = 0; j < mx; j++) {
if((atk1(i) & j) || (atk1(j) & i)) continue;
f[2][i][j] += f[1][i][0];
}
}
for(int i = 3; i <= R; i++)
{
memset(f[(i + 1) % 3], 0, sizeof(f[(i + 1) % 3]));
for(int j = 0; j < mx; j++)
for(int k = 0; k < mx; k++)
{
if((atk1(k) & j) || (atk1(j) & k)) continue;
for(int l = 0; l < mx; l++) {
if(!((atk1(l) & k) || (atk1(k) & l) || (atk2(l, k) & j) || (atk2(j, k) & l))) {
add(f[i % 3][j][k], f[(i + 2) % 3][k][l]);
}
}
}
}
int res = 0;
for(int i = 0; i < mx; i++) {
for(int j = 0; j < mx; j++) {
if((atk1(i) & j) || (atk1(j) & i)) continue;
else add(res, f[R % 3][i][j]);
}
}
cout << res << '\n';
return 0;
}
参考文献: