TopCoder SRM 532 Div1 Medium DengklekBuildingRoads

問題

N個の町があり、1番からN番の番号がついている。
そこに双方向に通行可能な道路M本を引く。

道路は、異なる町A,Bについて|A-B|≦Kのときに引くことができる。
また、全ての道路を引き終えた後で、全ての町から出ている道路の数は偶数でなくてはならない。
同じ町のペアに複数本の道路を引くこともできる。

このとき、道路の引き方は何通りあるか、mod 10^9+7で求めよ。

制約条件

N,M≦30
K≦8

方針

動的計画法による。
dp[i][j][mask][k]を、
町i番目を見ていて、j本今までに道路を引いて、
直前のK+1個の町の奇数本道路がつながれている町がmaskであらわされたときの場合の数としたい。

i番目の町からk番目の町へ道路をひいていってテーブルを更新したいので、
この場合の数を漏れなく重複なく数えるために、kを0からKまで更新してやることにする。
これで通るのだけれど上手く日本語で説明できない。

ソースコード

const int mod = (int)1e9 + 7;
int dp[31][31][1<<9][9];
struct DengklekBuildingRoads{
	int numWays(int N, int M, int K){
		dp[0][0][0][0]=1;
		for(int i=1;i<N;i++){
			rep(j,M+1)rep(mask,1<<K+1)if((mask&1)==0)
				(dp[i][j][mask>>1][0]+=dp[i-1][j][mask][min(i-1,K)])%=mod;
			rep(l,min(K,i))rep(j,M+1)rep(mask,1<<K+1)for(int r=0;r+j<=M;r++)
				(dp[i][j+r][mask^(r&1)<<K^(r&1)<<K-l-1][l+1]+=dp[i][j][mask][l])%=mod;
		}
		return dp[N-1][M][0][min(K,N-1)];
	}
};