TopCoder SRM 532 Div2 Hard DengklekPaintingSquares

ここらへんは割と順調。
http://community.topcoder.com/stat?c=problem_statement&pm=11765

問題

2次元グリッドのサイズNxMが与えられる。
各セルを以下の条件を満たすように塗り分けたい。

• 各セルは色つきか色なしのいずれかの状態である。
• 色つきセルは、四方の隣接セルにおける色つきセルの数が偶数でなければならない。

塗り分け方の組み合わせ数を答えよ。

解法

グリッドサイズの幅Mは8までと小さい。
よって、DPの状態としてdp[行][前の行の色の状態][前の行のパリティ]として上の行から順にDPすればよい。
[前の行の色の状態]は行の色の状態をbitmapで持つ。
[前の行のパリティ]は、前の行のうち色つきマスについて、隣接マスの偶奇をbitmapでもつ。

[前の行のパリティ]のbitが立っている場合、前の行の色つきマスの隣接セルを偶数個色つきにするため、その下のマスも色つきでなければならない。

あとはO(N 4^M)でBitDPするだけ。

ll mo=1000000007;
ll dp[102][256][256];

class DengklekPaintingSquares {
	public:
	int numSolutions(int H, int W) {
		int y,mask,par,x,nmask;
		ZERO(dp);
		dp[0][0][0]=1;
		FOR(y,H) {
			FOR(mask,1<<W) FOR(par,mask+1)  {
				if((mask|par)!=mask) continue;
				if(dp[y][mask][par]==0) continue;
				FOR(nmask,1<<W) {
					if(mask & (nmask^par)) continue;
					int np=0;
					FOR(x,W) {
						if(!(nmask&(1<<x))) continue;
						int b=!!(mask&(1<<x));
						if(x>0) b^=!!(nmask & (1<<(x-1)));
						if(x<W-1) b^=!!(nmask & (1<<(x+1)));
						np |= b<<x;
					}
					dp[y+1][nmask][np] = (dp[y+1][nmask][np] + dp[y][mask][par])%mo;
				}
			}
		}
		
		ll ret=0;
		FOR(mask,1<<W) ret += dp[H][mask][0];
		return ret%mo;
	}
};

まとめ

BitDPを2つ重ねるのは珍しいな。