题解：CF342D Xenia and Dominoes

· · 题解

显然做法是计数 dp。

把 O 视作障碍，设 O 的坐标为 (x,y)，若 (x-1,y),(x-2,y) 均无障碍且没有出界则可以放置一个可滑动的多米诺，其他方向亦然。然后我们枚举哪些位置放这样的多米诺，等价于令这两个位置为障碍然后 dp 求答案即可。

但这样会算重，但只有四个方向，所以可以直接暴力容斥算。

再想如何 dp。注意到行数很少，且一个多米诺顶多管两列，我们考虑按列 dp。第 j 列多米诺的放置情况取决于 j-1 列的放置情况，所以需要状态压缩记录第 j 列的多米诺放置情况。

先考虑没有障碍的情况。设当前 dp 到第 j 列。多米诺可以横着放，要求 (i,j-1) 对应的状态为未填 ；也可以竖着放，要求 (i-1,j) 为已填，因为多米诺只能管两列。一共 3 行，所以状态为 0 \sim 7，可以想到状态 s 可以从前一列的 7-s 转移过来，对应的放置情况为全部横着放。若第 j 列存在竖着放的情况，也就是状态为 3 或 6 时，还可以从状态 7 转移过来；状态为 7 时还可以从状态 3,6 转移过来。

考虑存在障碍的情况。我们先算出第 j 列的障碍情况 s。如果 (i,j) 存在障碍的话，我们在第 j 列 dp 时要把这个位置当作没有放多米诺，因为 (i,j-1) 必须放；但是在第 j+1 列 dp 时要把这个位置当作已经放了多米诺，因为这个位置不能填。然后枚举第 j 列多米诺放置情况 k，若 k \& s>0 显然是不合法的。而对于下一列来说，其实际状态为 k \oplus s。

所以有 f_{i,k \oplus s}=f_{i-1,7-k}。还有一些上述提到的特殊转移特判一下就可以了。

容斥是 2^4，状压是 2^3，因此复杂度是 O(Kn)，其中 K=2^7。

代码：

#include<bits/stdc++.h>
using namespace std;
#define N 10005
#define M 10
#define int long long
const int mod = 1e9+7;
int n=3,m,i,j,ans,x,y,L,R,U,D,f[N][M];
char mp[M][N];
int dp(){
    memset(f,0,sizeof(f));
    f[0][7]=1;
    for(int i=1;i<=m;i++){
        int s=0;
        for(int j=1;j<=n;j++){
            if(mp[j][i]=='X') s^=(1<<(j-1));
        }
        for(int j=0;j<=7;j++){
            if(s&j) continue;
            int ns=(j^s);
            f[i][ns]=(f[i][ns]+f[i-1][7-j])%mod;
            if(j==3 || j==6) f[i][ns]=(f[i][ns]+f[i-1][7])%mod;
            if(j==7) f[i][ns]=(f[i][ns]+f[i-1][3]+f[i-1][6])%mod;
        }
    }
    return f[m][7];
}
signed main(){
    scanf("%lld",&m);
    for(i=1;i<=n;i++) scanf("%s",mp[i]+1);
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++) if(mp[i][j]=='O') x=i,y=j;
    }
    mp[x][y]='X';
    for(L=0;L<=1;L++){
        if(L && (y<3 || mp[x][y-1]=='X' || mp[x][y-2]=='X')) continue;
        for(R=0;R<=1;R++){
            if(R && (y>m-2 || mp[x][y+1]=='X' || mp[x][y+2]=='X')) continue;
            for(U=0;U<=1;U++){
                if(U && (x<3 || mp[x-1][y]=='X' || mp[x-2][y]=='X')) continue;
                for(D=0;D<=1;D++){
                    if(D && (x>1 || mp[x][y+1]=='X' || mp[x][y+2]=='X')) continue;
                    if(!L && !R && !U && !D) continue;                  
                    if(L) mp[x][y-1]='X',mp[x][y-2]='X';
                    if(R) mp[x][y+1]='X',mp[x][y+2]='X';
                    if(U) mp[x-1][y]='X',mp[x-2][y]='X';
                    if(D) mp[x+1][y]='X',mp[x+2][y]='X';
                    int res=dp();
                    if((L+R+U+D)&1) ans=(ans+res)%mod;
                    else ans=(ans-res+mod)%mod;
                    if(L) mp[x][y-1]='.',mp[x][y-2]='.';
                    if(R) mp[x][y+1]='.',mp[x][y+2]='.';
                    if(U) mp[x-1][y]='.',mp[x-2][y]='.';
                    if(D) mp[x+1][y]='.',mp[x+2][y]='.';
                }
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}