TopCoder SRM 514 Div1 Medium: MagicalGirlLevelTwoDivOne

解法

左上のN*Mの長方形内の遇奇を考えれば良い。
i行目の和が奇数になるパターンを組み合わせて、i行目までの各列の和が最終的に奇数になるようにビットDPすれば良い。

コード

import java.util.Arrays;

public class MagicalGirlLevelTwoDivOne {

	private final int MOD = (int) 1e9 + 7;

	public int theCount(String[] input, int N, int M) {
		int H = input.length;
		int W = input[0].length();
		char[][] palette = new char[H][];
		for (int i = 0; i < H; i++) {
			palette[i] = input[i].toCharArray();
		}

		long[][] even = new long[N][M];// [i][j]を偶数とした場合のパターン数
		long[][] odd = new long[N][M];// [i][j]を奇数とした場合のパターン数
		for (int i = 0; i < N; i++) {
			Arrays.fill(even[i], 1);
			Arrays.fill(odd[i], 1);
		}

		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				int n = i % N;
				int m = j % M;

				if (palette[i][j] == '.') {
					odd[n][m] *= 5;
					odd[n][m] %= MOD;
					even[n][m] *= 4;
					even[n][m] %= MOD;
				} else {
					int num = palette[i][j] - '0';
					if (num % 2 == 1) {
						even[n][m] = 0;
					} else {
						odd[n][m] = 0;
					}
				}
			}
		}

		// [i][bit]:= i行目の奇遇の並びがbitのようになる時のパターン数（奇数なら1）
		long[][] transition = new long[N][1 << M];
		for (int i = 0; i < N; i++) {
			// i行目を見る
			for (int bit = 0; bit < (1 << M); bit++) {
				// i行目の和が偶数ならば条件を満たさないのでスルー
				if (Integer.bitCount(bit) % 2 == 0) {
					continue;
				}

				transition[i][bit] = 1;
				for (int j = 0; j < M; j++) {
					if (((bit >> j) & 1) == 1) {
						transition[i][bit] *= odd[i][j];
						transition[i][bit] %= MOD;
					} else {
						transition[i][bit] *= even[i][j];
						transition[i][bit] %= MOD;
					}
				}
			}
		}

		// dp[i+1][bit]:= i行目までの各列の和がbitのようになっている時のパターン数
		long[][] dp = new long[N + 1][1 << M];
		dp[0][0] = 1;
		for (int i = 0; i < N; i++) {
			for (int prevBit = 0; prevBit < (1 << M); prevBit++) {
				// i-1行目までの和がprevBitのようになっている時を考える。
				for (int nowBit = 0; nowBit < (1 << M); nowBit++) {
					// i行目がnowBitのようになっているとする
					if (Integer.bitCount(nowBit) % 2 == 0) {
						continue;
					}
					int nextBit = prevBit ^ nowBit;
					dp[i + 1][nextBit] += dp[i][prevBit]
							* transition[i][nowBit];
					dp[i + 1][nextBit] %= MOD;
				}
			}
		}

		// N-1行目までの各列の和は全て整数になってなければならないので、
		// dp[N][111...111]に求めるべき答が入っているはずである
		return (int) dp[N][(1 << M) - 1];
	}
}