CF342D Xenia and Dominoes

제목

이것을 찍어 문제를 보다.

2. 해법

우선 빈자리가 없으면 어떻게 할 것인가를 고려한다.× 2 1\times2 1×2의 골패는 상압을 고려할 수 있다. dp[i][s]dp[i][s]dp[i][s]를 제ii열로 하는 상태는 ss이고 앞의 i-3-1i-1i-3열을 모두 채운다(골패는 이 열과 앞의 열만 관리할 수 있기 때문이다)
어떻게 옮겨요?우선 채울 수 없는 칸을 고려하지 않으면 모든 상태가 상층(7-4-s)(7-4-s)(7-4-s)로 옮겨진다(가로채기, 대괄호가 상층을 강조하는 상압), 333과 666은 (7)(7)(세로채움), 777은 33 또는 666(가로세로 결합)로 옮겨진다(가로세로 결합).만약에 채울 수 없는 칸을 고려한다면 채울 수 없는 상압이 cu r cur cur라고 가정하고 고려하지 않을 때 j j j의 결과는 j ∣ cu r j| cur j ∣ cur에 저장해야 하며 j j와 cu r cur cur는 교차하지 않는다.
마지막으로 빈자리를 고려하여 네 방향에서 골패를 놓을 수 있는 방향을 찾아내고 그 중 일부를 골라 칸을 채우지 못하도록 강요하면 이런 방안수를 계산할 수 있다.분명히 이렇게 하면 무거운 셈이다. 지수급으로 밀어내면 문제를 잘 해결할 수 있다.

#include 
#include 
#include 
using namespace std;
const int M = 10005;
const int MOD = 1e9+7;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,x,y,a[4][M],b[4][M],dp[M][8];char s[4][M];
int dx[4]={1,-1},dy[4]={0,0,1,-1};
int work()
{
	memset(dp,0,sizeof dp);
	dp[0][7]=1;
	for(int i=1;i<=n;i++)
	{
		int cur=b[1][i]+b[2][i]*2+b[3][i]*4;
		for(int j=0;j<8;j++)
		{
			if(j&cur) continue;
			dp[i][j|cur]=dp[i-1][7-j];
			if(j==3 || j==6)
				dp[i][j|cur]=(dp[i][j|cur]+dp[i-1][7])%MOD;
			if(j==7)
			{
				dp[i][j|cur]=(dp[i][j|cur]+dp[i-1][3])%MOD;
				dp[i][j|cur]=(dp[i][j|cur]+dp[i-1][6])%MOD;
			}
		}
	}
	return dp[n][7];
}
void fuck()
{
	vector<int> way;int ans=0;
	for(int i=0;i<4;i++)
	{
		int tx=x+2*dx[i],ty=y+2*dy[i];
		if(tx>=1 && tx<=3 && ty>=1 && ty<=n && !a[tx][ty] && !a[x+dx[i]][y+dy[i]])
			way.push_back(i);
	}
	for(int i=1;i<(1<<way.size());i++)
	{
		memcpy(b,a,sizeof a);
		for(int j=0;j<way.size();j++)
			if(i&(1<<j))
				b[x+dx[way[j]]][y+dy[way[j]]]=b[x+2*dx[way[j]]][y+2*dy[way[j]]]=1;
		if(__builtin_popcount(i)&1)
			ans=(ans+work())%MOD;
		else
			ans=(ans-work()+MOD)%MOD;
	}
	printf("%d
",ans);
}
signed main()
{
	n=read();
	for(int i=1;i<=3;i++)
	{
		scanf("%s",s[i]+1);
		for(int j=1;j<=n;j++)
		{
			if(s[i][j]=='X')
				a[i][j]=1;
			if(s[i][j]=='O')
			{
				a[i][j]=1;
				x=i;y=j;
			}
		}
	}
	fuck();
}