51Nod1626 B君的梦境 状压dp 矩阵

原文链接https://www.cnblogs.com/zhouzhendong/p/51Nod1626.html

题目传送门 - 51Nod1626

题意

题解

　　首先考虑形象的想象本题中的思维空间。我们把整个 2*2*3*n 的四维空间看作 n 个 2*2*3 的三维空间顺次排列。考虑到 1*1*1*2 的方块，我们如果把边长 2 放在第 4 维上，相当于是填充了连续两个三维空间的对应位置。否则，边长 1 就放在了第 4 维上，相当于在一个三维空间中填充 1*1*2 的方块。

　　然后我们考虑状压 DP 。状态压缩当前三维空间的被填充状态。显然有 $2^{2\times 2\times 3}=4096$ 种情况。然后，我们考虑通过旋转、对称删除一些重复的状态，通过黑白染色删除一些没用的状态，最后剩下的状态数很少了。然后矩阵快速幂即可。

　　如果要更加具体地了解如何删除状态，参见代码或者原题的题解。

代码

#include <bits/stdc++.h>

#define Hash(a,b,c) Ha[a][b][c]

using namespace std;

typedef long long LL;

const int N=105,mod=1e9+7;

LL n;

int t=0,a[N],Min[1<<12],ID[1<<12],Ha[5][5][5];

struct Mat{

	int v[N][N];

	Mat(){}

	Mat(int x){

		memset(v,0,sizeof v);

		for (int i=1;i<=t;i++)

			v[i][i]=x;

	}

}M(0);

Mat operator * (Mat A,Mat B){

	Mat C(0);

	for (int i=1;i<=t;i++)

		for (int j=1;j<=t;j++)

			for (int k=1;k<=t;k++)

				C.v[i][j]=(1LL*A.v[i][k]*B.v[k][j]+C.v[i][j])%mod;

	return C;

}

Mat Pow(Mat x,LL y){

	Mat ans(1);

	for (;y;y>>=1,x=x*x)

		if (y&1LL)

			ans=ans*x;

	return ans;

}

void SwapD(int &v,int i,int j){

	if (((v>>i)^(v>>j))&1)

		v^=(1<<i)^(1<<j);

}

int checkWB(int s){

	int ans=0;

	for (int i=1;i<=2;i++)

		for (int j=1;j<=2;j++)

			for (int k=1;k<=3;k++)

				if (s>>Hash(i,j,k)&1)

					if ((i+j+k)&1)

						ans++;

					else

						ans--;

	return ans==0;

}

int calc(int s){

	int res=s;

	for (int t=0;t<4;t++){

		int v=s;

		if (t&1)

			for (int j=1;j<=2;j++)

				for (int k=1;k<=3;k++)

					SwapD(v,Hash(1,j,k),Hash(2,j,k));

		if (t>>1)

			for (int i=1;i<=2;i++)

				for (int j=1;j<=2;j++)

					SwapD(v,Hash(i,j,1),Hash(i,j,3));

		for (int d=0;d<4;d++,res=min(res,v))

			for (int i=1;i<=3;i++){

				SwapD(v,Hash(1,1,i),Hash(1,2,i));

				SwapD(v,Hash(1,2,i),Hash(2,2,i));

				SwapD(v,Hash(2,2,i),Hash(2,1,i));

			}

	}

	return res;

}

int dx[6]={ 0, 0, 0, 0, 1,-1},_x[6];

int dy[6]={ 0, 0, 1,-1, 0, 0},_y[6];

int dz[6]={ 1,-1, 0, 0, 0, 0},_z[6];

void GetXYZ(){

	int cnt=0;

	for (int i=1;i<=2;i++)

		for (int j=1;j<=2;j++)

			for (int k=1;k<=3;k++)

				if ((i+j+k)&1)

					cnt++,_x[cnt]=i,_y[cnt]=j,_z[cnt]=k;

}

void GetM(int S,int v,int t){

	if (t>6){

		M.v[S][ID[Min[v]]]++;

		return;

	}

	GetM(S,v,t+1);

	int x=_x[t],y=_y[t],z=_z[t],xx,yy,zz;

	if (v>>Hash(x,y,z)&1)

		return;

	for (int i=0;i<6;i++){

		xx=x+dx[i],yy=y+dy[i],zz=z+dz[i];

		if ((1<=xx&&xx<=2&&1<=yy&&yy<=2&&1<=zz&&zz<=3)&&(~v>>Hash(xx,yy,zz)&1))

			GetM(S,v^(1<<Hash(x,y,z))^(1<<Hash(xx,yy,zz)),t+1);

	}

}

int main(){

	int sz=1<<12;

	for (int i=1;i<=2;i++)

		for (int j=1;j<=2;j++)

			for (int k=1;k<=3;k++)

				Ha[i][j][k]=(i-1)*6+(j-1)*3+k-1;

	for (int i=0;i<sz;i++)

		if (checkWB(i))

			if ((Min[i]=calc(i))==i)

				a[++t]=i,ID[i]=t;

	GetXYZ();

	for (int i=1;i<=t;i++)

		GetM(i,a[i]^(sz-1),1);

	scanf("%lld",&n);

	M=Pow(M,n);

	printf("%d",M.v[ID[Min[sz-1]]][ID[Min[sz-1]]]);

	return 0;

}