洛谷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;
}