SRM 555 div1 med XorBoard

問題名がめっちゃヒント。

問題

TopCoder Statistics - Problem Statement

H 行 W 列のグリッドが与えられる。最初グリッド上のセルはすべて 0 であるが, rowCount 回どこかの行を選んでそこのすべての 0 を 1 に変え, 1 を 0 に変える, という作業をしたのち, colCount 回どこかの列を選んでそこのすべての 0 を 1 に変え, 1 を 0 に変える, という作業をする。
この作業を終えた後, 1 の値のセルが S 個あるような場合の数を求めよ。

解法

行で 1 にするものの数と 列で 1 にするものの数を決めると, 最後に 1 になっているものの数は, XOR で与えられるので, 問題は「H 個の中から h 個を 1 にする(ひっくり返す操作は cnt 回できる) 方法は何通りあるか」という部分問題に簡単化できます。

後はこの問題が解ければ良いですが,

• H 個の中から どの h 個を選ぶかで comb[H][h] 通り
• 選んだ h 個に何回ずつひっくり返す作業を対応させるかを考える
  • h 個は奇数回ひっくり返すので cnt -= h しておく
  • こう考えるとすべてのセルは偶数回ずつひっくり返すことになるので, cnt が奇数だったら NG
  • そうでない場合は dp[i][j] = (i 個目までで j 回ひっくり返すのを消費するような場合の数) というのを前計算しておいて dp[H][cnt/2] を求める
• 上記 2 つを掛け算したものが答え

const int MOD = 555555555;
const int MAXN = 1600;
ll dp[MAXN][MAXN];
ll comb[MAXN][MAXN];

ll calc(int H, int Rcount, int h) {
    ll ret = comb[H][h];
    int rest = Rcount-h;
    if (rest < 0 || rest%2 == 1) return 0;
    (ret *= dp[H][rest/2]) %= MOD;
    return ret;
}

class XorBoard {
public:
    int count(int H, int W, int Rcount, int Ccount, int S) {
        for (int i = 0; i < MAXN; i++) {
            comb[i][0] = 1;
            for (int j = 1; j <= i; j++) {
                comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % MOD;
            }
        }
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        for (int i = 1; i < MAXN; i++) {
            for (int j = 0; j < MAXN; j++) {
                dp[i][j] = dp[i-1][j];
                if (j > 0) (dp[i][j] += dp[i][j-1]) %= MOD;
            }
        }
        ll ans = 0;
        for (int h = 0; h <= H; h++) for (int w = 0; w <= W; w++) {
            int cnt = h*(W-w) + (H-h)*w;
            if (cnt != S) continue;
            (ans += calc(H, Rcount, h)*calc(W, Ccount, w)%MOD) %= MOD;
        }
        return ans;
    }
};