P5005题解

· · 题解

谨以此篇题解纪念我首个完全独立思考 AC 的紫题。

首先，本题一眼看上去就是个炮兵阵地加强版，然后数据范围 M\leq 6，铁状压。

显然，我们需要设计一个3维动态规划，维护当前行号，当前行状态，上一行状态（因为马的攻击范围只有两行）。我们令 dp_{i,j,k} 代表当前看到第 i 行，本行状态为 j， 上一行状态为 k 的方案数，ok_{i,j,k} 代表状态是否合法。状态转移方程即为：

dp_{i,j,k}=\sum_q [ok_{q,j,k}]dp_{i-1,q,j}

最主要的是 ok_{i,j,k} 如何求，我们可以通过位运算的左移右移来表示，注意，马的攻击不一定是相互的（因为有马脚）。我们可以首先预处理出所有局面不可以放的位置，以及上下两行冲突的局面方便判断。预处理复杂度 \Theta(2^{m+1}m)。

这里是关键部分的代码，其中后两行是判断若该点放置的话会不会影响前面的局面，即能够攻击到上面的马：

for (int k=0; k<=((1<<m)-1); k++) {
        for (int l=0; l<=((1<<m)-1); l++) {
            for (int j=0; j<m; j++) {
                if ((k>>1)&(1<<j))if (!((l>>1)&(1<<j)))can[k][l]|=1<<j;
                if ((k<<1)&(1<<j))if (!((l<<1)&(1<<j)))can[k][l]|=1<<j;
                if ((l>>2)&(1<<j))if (!((l>>1)&(1<<j)))can[k][l]|=1<<j;
                if ((l<<2)&(1<<j))if (!((l<<1)&(1<<j)))can[k][l]|=1<<j;
                if (!(l&(1<<j)))if (k>>1&(1<<j))can[k][l]|=1<<j;
                if (!(l&(1<<j)))if (k<<1&(1<<j))can[k][l]|=1<<j;

            }
        }
    }

随即注意到本题空间限制仅 1\texttt{Mb}，所以滚动数组一下即可。

AC Code：

#include <bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;

int dp[2][1<<6+1][1<<6+1],can[1<<6+1][1<<6+1];
bool ok[1<<6+1][1<<6+1];

string abc(ll s,ll dep) {
    if (dep==2)return s%2?"1":"0";
    return abc(s/2,dep+1)+(s%2?"1":"0");
}

int main() {
    int n,m;
    cin >> n >> m;
    for (int k=0; k<=((1<<m)-1); k++) {
        for (int l=0; l<=((1<<m)-1); l++) {
            for (int j=0; j<m; j++) {
                if ((k>>1)&(1<<j))if (!((l>>1)&(1<<j)))can[k][l]|=1<<j;
                if ((k<<1)&(1<<j))if (!((l<<1)&(1<<j)))can[k][l]|=1<<j;
                if ((l>>2)&(1<<j))if (!((l>>1)&(1<<j)))can[k][l]|=1<<j;
                if ((l<<2)&(1<<j))if (!((l<<1)&(1<<j)))can[k][l]|=1<<j;
                if (!(l&(1<<j)))if (k>>1&(1<<j))can[k][l]|=1<<j;
                if (!(l&(1<<j)))if (k<<1&(1<<j))can[k][l]|=1<<j;

            }
        }
    }
    for (int k=0; k<=((1<<m)-1); k++) {
        for (int l=0; l<=((1<<m)-1); l++) {
            ok[k][l]=1;
            for (int j=0; j<m; j++) {
                if (l&(1<<j))
                    if ((k<<2)&(1<<j))
                        if (!((k<<1)&(1<<j)))
                            ok[k][l]=0;
                if (l&(1<<j))
                    if ((k>>2)&(1<<j))
                        if (!((k>>1)&(1<<j)))

                            ok[k][l]=0;

                if (k&(1<<j))
                    if ((l<<2)&(1<<j))
                        if (!((l<<1)&(1<<j)))
                            ok[k][l]=0;
                if (k&(1<<j))
                    if ((l>>2)&(1<<j))
                        if (!((l>>1)&(1<<j)))

                            ok[k][l]=0;
            }
        }
    }
    for (int k=0; k<=((1<<m)-1); k++)dp[1][0][k]=1;

    for (int l=0; l<=((1<<m)-1); l++)
        for (int k=0; k<=((1<<m)-1); k++)
            if (ok[k][l]) {
                dp[0][k][l]+=dp[1][0][k];
                dp[0][k][l]%=mod;
            }

    for (int i=3; i<=n; i++) {
        memset(dp[i%2],0,sizeof(dp[i%2]));
        for (int j=0; j<=((1<<m)-1); j++) {
            for (int l=0; l<=((1<<m)-1); l++) {
                for (int k=0; k<=((1<<m)-1); k++) {

                    if (!ok[k][l])continue;
                    if (!ok[l][j])continue;
                    if (can[k][l]&j)continue;

                    dp[i%2][l][j]+=dp[i%2^1][k][l];
                    dp[i%2][l][j]%=mod;
                }
            }
        }
    }
    ll ans=0;
    for (int j=0; j<=((1<<m)-1); j++) {
        for (int k=0; k<=((1<<m)-1); k++) {
            if (ok[j][k]) {
                ans+=dp[n%2][j][k];
                ans%=mod;
            }

        }
    }
    cout << ans;
    return 0;
}