题解：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

。

代码：

CPP

#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;
}

题解：CF342D Xenia and Dominoes

文章操作

相关推荐

评论

题解：CF342D Xenia and Dominoes