TopCoder SRM 514 Div1 Medium MagicalGirlLevelTwoDivOne

途中までは行けたけど最後までは自力でたどり着けず。
http://community.topcoder.com/stat?c=problem_statement&pm=11482

問題

2次元グリッドP中に1～9の数字が書かれている。
ここでこのグリッドは以下の要素を満たさなければならない。

• 連続する縦方向のn要素の和は奇数である
• 連続する縦方向のm要素の和は偶数である

グリッド中いくつかのセルは数字が未定である。
これらのセルに1～9の数字を入れた場合、有効なグリッドの組み合わせ数を答えよ。

解法

条件よりP[y][x]とP[y+n][x]の偶奇は等しく、P[y][x]とP[y][x+m]の偶奇は等しくなければならない。
結果的に、P[0][0]～P[n-1][m-1]の偶奇さえ定まれば全体のグリッドの偶奇が定まる。
よってP[0][0]～P[n-1][m-1]の偶奇を求めていこう。

y行目までの各列の総和の偶奇をbitmaskで保持しながらDPしていき、最終的にbitmaskが全部set = 各列奇数となる組み合わせを求めればよい。
未定のセルについては、奇数なら5通り(1,3,5,7,9)、偶数なら4通り(2,4,6,8)の値が入る。

ll mo=1000000007;
ll p[2][2501];
ll rowdp[11][1<<11];
ll rowdp2[11][1<<11];

class MagicalGirlLevelTwoDivOne {
	public:
	int W,H;
	int num[51][51];
	int ms[51][51];
	
	int theCount(vector <string> palette, int n, int m) {
		int x,y,i,mask,mask2;
		H=palette.size();
		W=palette[0].size();
		
		p[0][0]=p[1][0]=1;
		FOR(i,2500) p[0][i+1]=p[0][i]*4%mo,p[1][i+1]=p[1][i]*5%mo;
		
		ZERO(num);
		ZERO(ms);
		
		FOR(y,H) FOR(x,W) {
			if(palette[y][x] == '.') num[y%n][x%m]++;
			if(isdigit(palette[y][x])) ms[y%n][x%m] |= 1<<(palette[y][x]%2);
		}
		
		ZERO(rowdp);
		ZERO(rowdp2);
		rowdp2[0][0]=1;
		
		FOR(y,n) FOR(mask,1<<m) if(__builtin_popcount(mask)%2) {
			rowdp[y][mask]=1;
			FOR(x,m) {
				if(mask & (1<<x)) {
					if(ms[y][x]&1) rowdp[y][mask]=0;
					else rowdp[y][mask]=rowdp[y][mask]*p[1][num[y][x]]%mo;
				}
				else {
					if(ms[y][x]&2) rowdp[y][mask]=0;
					else rowdp[y][mask]=rowdp[y][mask]*p[0][num[y][x]]%mo;
				}
			}
			FOR(mask2,1<<m) rowdp2[y+1][mask^mask2] = (rowdp2[y+1][mask^mask2] + rowdp2[y][mask2]*rowdp[y][mask])%mo;
		}
		
		return rowdp2[n][(1<<m)-1];
	}
};

まとめ

P[n-1][m-1]の小さなグリッドの問題までは落とし込めたけど、そこからbitDPに持っていけなかった…。