TopCoder SRM 532 Div2 Hard DengklekPaintingSquares

問題

NxMのグリッドがある。
それぞれのマスについて、色を塗るか塗らないか選ぶ。
色を全て塗り終えた後で、

• 色が塗られているマスに（上下左右に）隣接する色の塗られているマスの数はすべて偶数である

ような色の塗り方は何通りあるか、求めよ。

制約条件

N≦100
M≦8

方針

一列分を覚える動的計画法による。
それぞれのマスは、「色が塗られていない」「色が塗られていて、隣接する色のついたマスが偶数個」「色が塗られていて、隣接する色のついたマスが奇数個」の3通りに分けて覚えればよい。
一列分は、これを3進数としてコードして表現する。

これを1マスずつ更新していけばいい。

ソースコード

const int mod=(int)1e9+7;
int dp[2][9][20000];
struct DengklekPaintingSquares{
	int numSolutions(int N, int M){
		int pw[9], cur=0, next=1;
		pw[0]=1;
		rep(i,9)pw[i+1]=pw[i]*3;
		dp[0][M][0]=1;
		rep(i,N){
			memset(dp[next],0,sizeof(dp[next]));
			rep(j,pw[M])dp[next][0][j]=dp[cur][M][j];
			rep(j,M)rep(k,pw[M])if(dp[next][j][k]){
				int prev=k/pw[j]%3, left=j?k/pw[j-1]%3:-100;
				rep(nxt,2){
					if(prev==2&&nxt==0||prev==1&&nxt==1)continue;
					int nk=k+(nxt-prev)*pw[j];
					if(nxt&&(prev>0)+(left>0)==1)nk+=pw[j];
					if(nxt&&left==1)nk+=pw[j-1];
					if(nxt&&left==2)nk-=pw[j-1];
					(dp[next][j+1][nk]+=dp[next][j][k])%=mod;
				}
			}
			swap(cur, next);
		}
		int ans=0;
		rep(i,pw[M]){
			rep(j,M)if(i/pw[j]%3==2)goto FAIL;
			(ans+=dp[cur][M][i])%=mod;
			FAIL:;
		}
		return ans;
	}
};