【XSY3270】Domino Colorings（轮廓线dp，状压）

若已经知道了每个格子的颜色，我们可以用轮廓线 DP（类似插头 DP）判断棋盘是否能被多米诺骨牌填满，设 d p [ S ] dp[S] dp[S] 表示是否存在某种填法使得轮廓线每个位置是否被填的状态为 S S S 即可。

现在我们需要枚举每个格子的颜色，同时还要判断能否被填，所以我们要记录一维表示 d p [ S ] dp[S] dp[S] 数组。

为了转移时维护这一数组，我们还要记录轮廓线上每个格子的颜色。

于是设 f ( i , j , c , s ) f(i,j,c,s) f(i,j,c,s) 表示考虑到 ( i , j ) (i,j) (i,j)，轮廓线上格子颜色的状压为 c c c， d p [ S ] dp[S] dp[S] 数组的状压为 s s s 的方案数。

有点像 DP 套 DP（

至于为什么 f ( i , j ) f(i,j) f(i,j) 的状态数可以接受：

如图，假设 ( i , j ) (i,j) (i,j) 是当前的箭头所指的格子，那么轮廓线就是图中红框区域：（我把整个棋盘横竖交换了，这样我习惯些）

对于某种 ( c , s ) (c,s) (c,s) 来说，假如如图的多米诺骨牌填法满足 ( c , s ) (c,s) (c,s) 的限制：

那么绿框部分的颜色和填法是不受 ( c , s ) (c,s) (c,s) 影响的，只要能填满就行。

换言之，无论 ( c , s ) (c,s) (c,s) 怎么取，如图框起来的绿色部分是不受 ( c , s ) (c,s) (c,s) 影响的，或者说 ( c , s ) (c,s) (c,s) 并没有记录绿框内填牌的状态：

又由于一种填色方案只对着一种 ( c , s ) (c,s) (c,s)，所以 ( c , s ) (c,s) (c,s) 的状态数顶多是黄框内的格子的颜色的状态数，即 2 2 n = 2 12 = 4096 2^{2n}=2^{12}=4096 22n=212=4096 种。

实际上的状态数肯定是比我们讨论的这个还小的，solution 实测说是 2000 2000 2000 多种。

时间复杂度 O ( n m 2 2 n log ⁡ 2 2 n ) = O ( n 2 m 2 2 n ) O(nm2^{2n}\log 2^{2n})=O(n^2m2^{2n}) O(nm22nlog22n)=O(n2m22n)。

#include<bits/stdc++.h>

#define ull unsigned long long

using namespace std;

namespace modular
{
	const int mod=1000000007;
	inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
	inline int dec(int x,int y){return x-y<0?x-y+mod:x-y;}
	inline int mul(int x,int y){return 1ll*x*y%mod;}
	inline void Add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);}
}using namespace modular;

inline int poww(int a,int b)
{
	int ans=1;
	while(b)
	{
		if(b&1) ans=mul(ans,a);
		a=mul(a,a);
		b>>=1;
	}
	return ans;
}

inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^'0');
		ch=getchar();
	}
	return x*f;
}

struct data
{
	int col;
	ull sta;
	data(){};
	data(int a,ull b){col=a,sta=b;}
};

bool operator < (data a,data b)
{
	if(a.col==b.col) return a.sta<b.sta;
	return a.col<b.col;
}

int n,m,maxS;

map<data,int>f[2];

int main()
{
	n=read(),m=read();
	maxS=(1<<n)-1;
	int u=1,v=0;
	f[u][data(0,1)]=1;
	for(int i=1;i<=m;i++)
	{
		for(int j=0;j<n;j++,swap(u,v))
		{
			f[v].clear();
			for(map<data,int>::iterator it=f[u].begin();it!=f[u].end();it++)
			{
				int c=(it->first).col;
				ull dps=(it->first).sta;
				ull ndps0=0,ndps1=0;
				for(int s=0;s<=maxS;s++) 
				{
					if((dps>>s)&1)
					{
						if((s>>j)&1)//上面没填 
						{
							if((c>>j)&1) ndps0|=(1ull<<(s^(1<<j)));
							else ndps1|=(1ull<<(s^(1<<j)));
						}
						else
						{
							if(j>0&&((s>>(j-1))&1))//跟左边填
							{
								if((c>>(j-1))&1) ndps0|=(1ull<<(s^(1<<(j-1))));
								else ndps1|=(1ull<<(s^(1<<(j-1))));
							}
							ndps0|=(1ull<<(s^(1<<j))),ndps1|=(1ull<<(s^(1<<j)));//跟下面填 
						}
					}
				}
				Add(f[v][data((c|(1<<j))^(1<<j),ndps0)],it->second);
				Add(f[v][data(c|(1<<j),ndps1)],it->second);
			}
		}
	}
	int ans=0;
	for(map<data,int>::iterator it=f[u].begin();it!=f[u].end();it++)
	{
		ull s=(it->first).sta;
		if(s&1) Add(ans,it->second);
	}
	printf("%d\n",ans);
	return 0;
}