Typical DP Contest S - マス目

問題

幅w高さhのグリッドを、白黒に塗る。
左上および右下のマスは黒であり、左上から右下へ隣接する（辺を共有する）黒い正方形をたどっていけるような塗り方は何通りあるかmod 10^9 + 7で求めよ。

制約条件

w≦6
h≦100

方針

接続関係をもつDP.
dp[i][j]をi行目まで見たとき、接続関係がvectorのjで表されるときの塗り方の場合の数として、これを1行ずつ一気に塗って更新していく。

接続関係は「何列目と何列目が同一の連結成分にあるか」を数字で持てばよくて、
たとえば1, 3, 5がつながっている、2と6がつながっているときは
(1, 2, 1, 3, 1, 2)のようなベクトルを接続関係のベクトルとすればよい。
接続関係のベクトルを更新するときは、ナイーブにunion-findなんかを使ってつながっている頂点をマージし、その後座標圧縮するみたいなことを毎回やって間に合う。

ソースコード

const int mod = (int)1e9 + 7;
int h, w;
map<vi, int> dp[2];
 
int p[12];
int root(int x){
	return x == p[x] ? x : (p[x] = root(p[x]));
}
void merge(int a, int b){
	a = root(a); b = root(b);
	if(a > b) swap(a, b);
	if(a != b) p[b] = a;
}
 
int main(){
	cin >> h >> w;
	int cur = 0, next = 1;
	
	rep(i, 1 << h) if(i & 1){
		vi v(h);
		int c = 1;
		rep(j, h) if(i & 1 << j) v[j] = i && (i & 1 << j-1) ? v[j-1] : c++;
		dp[0][v] = 1;
	}
	
	rep(i, w-1){
		dp[next].clear();
		each(j, dp[cur]) rep(k, 1 << h){
			
			int c = h, to[12];
			const vi &v = j->first;
			vi nv(h);
			
			rep(l, 2*h) p[l] = l, to[l] = -1;
			rep(l, h){
				if(k & 1 << l) nv[l] = c++;
				if(l && (k & 1 << l) && (k & 1 << l-1)) merge(nv[l-1], nv[l]);
				if(v[l] && nv[l]) merge(v[l], nv[l]);
			}
			
			c = 2;
			to[0] = 0; to[1] = 1;
			rep(l, h) if(nv[l]){
				nv[l] = root(nv[l]);
				if(to[nv[l]] < 0) to[nv[l]] = c++;
				nv[l] = to[nv[l]];
			}
			
			if(to[root(1)] < 0) continue;
			(dp[next][nv] += j->second) %= mod;
		}
		swap(cur, next);
	}
	
	ll ans = 0;
	each(i, dp[cur]) if((i->first)[h-1] == 1)
		ans += i->second;
	cout << ans % mod << endl;
	
	return 0;
}