TopCoder SRM 555 Div1 Medium: XorBoard

問題

TopCoder Statistics - Problem Statement

コード

public class XorBoard {
    private final int MOD = 555555555;

    public int count(int H, int W, int Rcount, int Ccount, int S) {
	// パスカルの三角形
	int N = Math.max(W, H) * 2;
	int[][] nCm = new int[N][N];
	for (int i = 0; i < N; i++) {
	    nCm[i][0] = 1;
	    for (int j = 1; j <= i; j++) {
		nCm[i][j] = (nCm[i - 1][j - 1] + nCm[i - 1][j]) % MOD;
	    }
	}

	long ans = 0;
	for (int r = Rcount % 2; r <= Rcount && r <= H; r += 2) {
	    for (int c = Ccount % 2; c <= Ccount && c <= W; c += 2) {
		// r=最終的に反転している行の数
		// c=最終的に反転している列の数
		if (W * r + H * c - 2 * r * c != S) {
		    continue;
		}

		int cDup = (Ccount - c) / 2;// 重複して反転した列の数
		int rDup = (Rcount - r) / 2;// 重複して反転した行の数

		// Wの中からcDup個の列を重複ありで選ぶ組み合わせの数
		long cDupComb = nCm[W - 1 + cDup][cDup] % MOD;

		// Hの中からrDup個の列を重複ありで選ぶ組み合わせの数
		long rDupComb = nCm[H - 1 + rDup][rDup] % MOD;

		ans += (long) nCm[W][c] * cDupComb % MOD * nCm[H][r] % MOD
			* rDupComb % MOD;

	    }
	}

	return (int) (ans % MOD);
    }

}