TopCoder SRM602: BlackBoxDiv2

正面から見えるブロック数を N、横から見えるブロック数を Mとすると
N × M の長方形の全列全行にブロックが少なくとも１つあるような配置のパターン数が答えになる。

以下では、「すでにブロックが配置されている行の個数」×「着目している列」を状態にした動的計画法で解いている。

各列に対してブロックを置くとき

• ブロックが置かれている行にブロックを置く場合は「すでにブロックが配置されている行の個数」はそのまま
• ブロックが置かれていない行にブロックを置く場合は「すでにブロックが配置されている行の個数」が１つ増える

という事実を使ってテーブルを更新している。

行に１つもブロックが置かない場合を弾く必要があるのに注意。

public class BlackBoxDiv2 {
    const int mod = 1000000007;

    static int?[,] _choose = new int?[111, 111];
    static int Choose(int s, int t) {
        if (!_choose[s, t].HasValue) {
            int val = (t == 0 || t == s) ? 1 : Choose(s - 1, t - 1) + Choose(s - 1, t);
            if (val >= mod) val %= mod;
            _choose[s, t] = val;
        }
        return _choose[s, t].Value;
    }

    // Solve by DP
    public int count(string front, string side) {
        int RowNum = front.Count(c => c == 'B');
        int ColNum = side.Count(c => c == 'B');
        var dp = new long[RowNum + 1];
        dp[0] = 1;
        for (int i = 0; i < ColNum; i++) {
            var next = new long[RowNum + 1];
            for (int usedRowNum = 0; usedRowNum <= RowNum; usedRowNum++) {
                int notUsedRowNum = RowNum - usedRowNum;
                for (int newUse = 0; newUse <= notUsedRowNum; newUse++) {
                    long pattern = Choose(notUsedRowNum, newUse);
                    long val = dp[usedRowNum] * pattern % mod;
                    long choiseFree = (1L << usedRowNum) % mod;
                    if (newUse == 0) choiseFree = (choiseFree + mod - 1) % mod;
                    val = (val * choiseFree) % mod;
                    next[usedRowNum + newUse] += val;
                    next[usedRowNum + newUse] %= mod;
                }
            }
            dp = next;
        }
        return (int)dp[RowNum];
    }
}

以下は包除原理を使った解法。

「N × M の長方形の全列全行にブロックが少なくとも１つある」を満たさない条件は

• i 行目にブロックがひとつもない (1 <= i <= N)
• j 列目にブロックがひとつもない (1 <= j <= M)

のいずれかを一つでも満たす場合になる。

OR条件の計算になるため、包除原理を使うとAND条件の足し算引き算に帰着でき、AND条件でのパターン数は、２の「ブロックがあってもよいセルの個数」乗になるので簡単に計算できる。

もちろんそのまま包除原理を適用すると\(N+M\)個の条件があるため \(O(2^{N+M})\) でとても間に合わないが、「ブロックが一つも含まれない行の個数と列の個数」が同じものについては、まとめて計算できるため、\(O(NM)\)に落とせる。

    // Solve by Inclusion-Exclusion Principle
    public int count(string front, string side) {
        int RowNum = front.Count(c => c == 'B');
        int ColNum = side.Count(c => c == 'B');
        long ans = 0;
        for (int i = 0; i <= RowNum; i++) {
            for (int j = 0; j <= ColNum; j++) {
                long pattern = (long)BigInteger.ModPow(2, (RowNum - i) * (ColNum - j), mod);
                pattern = (pattern * Choose(RowNum, i)) % mod;
                pattern = (pattern * Choose(ColNum, j)) % mod;
                if ((i + j) % 2 == 0) {
                    ans = (ans + pattern) % mod;
                } else {
                    ans = (ans - pattern + mod) % mod;
                }
            }
        }
        return (int)ans;
    }