「操作によって出来上がるものが何通りあるか？」という問題では、まず判定問題を考える！(素振り)

問題概要

$H \times W$ のグリッドがあって、各マスは白または黒に塗られている。以下の操作を好きな順序で好きな回数だけ行った結果得られる盤面が何通り考えられるか、998244353 で割ったあまりを求めよ。

好きな行または好きな列を選び、それ上のマスをすべて白にする
好きな行または好きな列を選び、それ上のマスをすべて黒にする

制約

$1 \le H, W \le 10$

考えたこと

「操作によって出来上がるものが何通りあるか」という問題では、基本的に「異なる操作によって同じものができてしまう」というダブルカウントを真っ向から扱うことが険しいことが多い。

代わりに有効なのが「まずは判定問題を考える」ということ。つまり、初期盤面 S と完成させたい盤面 T とが与えられたときに、S を T にすることが可能かどうかを判定する問題を考えるとヒントがつかめることが多い気がする。そもそも作問の経緯自体がそういう風に作られてることも多そう。

判定問題

たとえば S が

.#.#.
###..
..##.
.#...
....#

で、T が

.....
#.#..
#.###
#####
....#

であったときに、S を T にできるかどうかを考えてみよう。さて今回の操作の特徴として「上書きしてしまう」というのがある。そういうのは後ろから考えると良いケースが多そう。というわけで T から考える。まず以下の「?」のところはなんであっても T にできることはわかる。そこを上書きしてしまえるからだ。

?????
#.#..
#.###
?????
....#

そうしたら「?」は取り去ってしまえると考えることができて、同様にして

?????
#?#?.
?????
?????
.?.?#

というところまで持ってこれる。この「?」はどうであっても T の状態にできるということだ。しかるに S と比較すると「?」以外のところは一致しているので、Yes ということになる。

T において「?」を取り去ってできる長方形において、どの列もどの行も同色でない状態になったときのパターンを見て
S と一致すれば Yes、一致しなければ No

という風になる。判定問題は解決した。

数え上げの指針

ここまで考えてくると、数え上げの指針も見えてくる。まず、「?」で埋められた盤面が、「?」を取り去ってできる長方形のどの列もどの行も同色というわけではないとき、canonical であると呼ぶことにしてみよう。このとき、以下のことが言える。

S について、「?」で埋める行と列を選んだとき、異なる選び方をしてできるパターン T1 と T2 がともに canonical であったとする。このとき、「?」の部分をどのように埋めたとしても、T1 と T2 とが一致することはない。

これは、T を決めたときに canonical な状態は一意に決まるからだ。これは「操作で出来上がる T として、canonical な状態ごとに分類して数える」という指針が有効そうであることを意味する。

「?」で埋める行と列を選ぶ方法は $2^{H+W}$ 通りある。そのそれぞれについて canonical かどうかを判定し、canonical であれば「?」の埋め方を数え上げることにする。

「?」の埋め方の数え上げ

残るは、行を a 個、列を b 個を選んだときに、「?」の埋め方が何通りあるかを数える問題となった。これ...なかなか気付かなかったんだけど、行と列を埋めつくしてしまう場合と、はみ出しがある場合とで、微妙に (というか結構) 違うっぽい！！！！！！！！

はみ出しがない場合

つまりは、 $a \times b$ の長方形グリッドを埋める方法を考える。例によって後ろから考えて、一度塗ったところは色が変わらないという設定で考える。漸化式っぽく考えてみる

dp1[ a ][ b ] := 長方形に「黒のライン」が存在するような場合の数
dp2[ a ][ b ] := 長方形に「黒のライン」が存在しないような場合の数

とする。dp2 については遷移が明快。黒のラインが存在しないのだったら、白のラインは存在しなければならない。しかもそれが縦方向にも横方向にも存在しなければならない。なぜなら縦方向だけにあったら、縦方向の黒ラインが存在することになってしまう (ここが実は長方形じゃない場合で詰まる部分だったりする)。そして縦に i 個、横に j 個の白ラインを取り除いたものが今度は「白のライン」が存在しないような場合の数となる。よって、

dp2[ a ][ b ] += C(a, i) × C(b, j) × dp2[ a - i ][ b - j ]　(1 <= i <= a-1、1 <= j <= b-1)
dp2[ a ][ b ] += 1　(全部白)

という風になる。dp1 については黒のラインが縦に i 個、横に j 個あるとすると

dp1[ a ][ b ] += C(a, i) × C(b, j) × dp2[ a - i ][ b - j ]　(i + j >= 1、i <= a-1、j <= b-1)
dp1[ a ][ b ] += 1　(全部黒)

という感じ。

はみ出しがある場合

はみ出しがあるときは、あるラインが全部黒であったとしても、はみ出しのところは白であって、実はそのライン上に黒く塗られたわけではない、みたいな状況がありうる。で、色々と大変なので、ちょっと違う数え方をしてみる。

はみ出したところを何色に塗るのかをあらかじめ決めてしまうことにする。縦方向から黒 i 個、白 a-i 個、横方向から白 j 個、黒 b-j 個とすると、黒黒と白白のところは黒・白にするしかないので、結局問題は

$i \times j$ な長方形で、縦方向には黒く塗る、横方向には白く塗る
塗る順序は自由に選べる
最終的な模様は何通りになるか

という問題になる。これはもう一度 DP とかでなんとかなる。

まとめ

前処理にかかる時間は、 $O(N^{4})$ とかそんな感じ。その元で全探索して $O(HW 2^{H+W})$ という感じ。

必死デバッグの跡

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

template<int MOD> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    constexpr int getmod() { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};

// 二項係数ライブラリ
template<class T> struct BiCoef {
    vector<T> fact_, inv_, finv_;
    constexpr BiCoef() {}
    constexpr BiCoef(int n) noexcept : fact_(n, 1), inv_(n, 1), finv_(n, 1) {
        init(n);
    }
    constexpr void init(int n) noexcept {
        fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1);
        int MOD = fact_[0].getmod();
        for(int i = 2; i < n; i++){
            fact_[i] = fact_[i-1] * i;
            inv_[i] = -inv_[MOD%i] * (MOD/i);
            finv_[i] = finv_[i-1] * inv_[i];
        }
    }
    constexpr T com(int n, int k) const noexcept {
        if (n < k || n < 0 || k < 0) return 0;
        return fact_[n] * finv_[k] * finv_[n-k];
    }
    constexpr T fact(int n) const noexcept {
        if (n < 0) return 0;
        return fact_[n];
    }
    constexpr T inv(int n) const noexcept {
        if (n < 0) return 0;
        return inv_[n];
    }
    constexpr T finv(int n) const noexcept {
        if (n < 0) return 0;
        return finv_[n];
    }
};

const int MOD = 998244353;
using mint = Fp<MOD>;
BiCoef<mint> bc;

int H, W;
vector<string> A;

int main() {
    bc.init(110);

    // 長方形
    vector<vector<mint>> all(15, vector<mint>(15, 0));
    auto bein = all;
    auto notin = all;
    for (int i = 0; i < 15; ++i) all[0][i] = all[i][0] = modpow(mint(2), i);
    for (int a = 1; a < 15; ++a) {
        for (int b = 1; b < 15; ++b) {
            notin[a][b] = 1;
            for (int i = 1; i < a; ++i) {
                for (int j = 1; j < b; ++j) {
                    notin[a][b] += notin[a-i][b-j] * bc.com(a, i) * bc.com(b, j);
                }
            }
        }
    }
    for (int a = 1; a < 15; ++a) {
        for (int b = 1; b < 15; ++b) {
            bein[a][b] = 1;
            for (int i = 0; i < a; ++i) {
                for (int j = 0; j < b; ++j) {
                    if (i + j == 0) continue;
                    bein[a][b] += notin[a-i][b-j] * bc.com(a, i) * bc.com(b, j);
                }
            }
            all[a][b] = notin[a][b] + bein[a][b];
        }
    }

    // はみ出しあり
    vector<vector<mint>> subsub(15, vector<mint>(15, 0));
    auto sub = subsub, part = subsub;
    for (int i = 0; i < 15; ++i) {
        subsub[1][i] = 1;
        subsub[i][1] = modpow(mint(2), i) - 1;
    }
    for (int s = 2; s < 30; ++s) {
        for (int a = 1; a < 15; ++a) {
            int b = s - a;
            if (b < 1 || b >= 15) continue;
            subsub[a][b] = 1;
            for (int i = 1; i < a; ++i) {
                subsub[a][b] += bc.com(a, i) * subsub[b][a-i];
            }
        }
    }
    for (int a = 0; a < 15; ++a) {
        for (int b = 0; b < 15; ++b) {
            if (a == 0) sub[a][b] = 1;
            else if (b == 0) sub[a][b] = 1;
            else sub[a][b] = subsub[a][b] + subsub[b][a];
        }
    }
    for (int i = 0; i < 15; ++i) part[0][i] = part[i][0] = modpow(mint(2), i);
    for (int a = 1; a < 14; ++a) {
        for (int b = 1; b < 14; ++b) {
            for (int i = 0; i <= a; ++i) {
                for (int j = 0; j <= b; ++j) {
                    part[a][b] += bc.com(a, i) * bc.com(b, j) *
                        sub[i][j] * sub[a-i][b-j];
                }
            }
        }
    }

    cin >> H >> W;
    A.resize(H);
    for (int h = 0; h < H; ++h) cin >> A[h];

    mint res = all[H][W];
    for (int bit = 0; bit < (1<<H)-1; ++bit) {
        vector<int> tate;
        for (int i = 0; i < H; ++i) if (!(bit & (1<<i))) tate.push_back(i);
        for (int bit2 = 0; bit2 < (1<<W)-1; ++bit2) {
            vector<int> yoko;
            for (int i = 0; i < W; ++i) if (!(bit2 & (1<<i))) yoko.push_back(i);

            bool ok = true;
            for (auto i : tate) {
                set<char> se;
                for (auto j : yoko) se.insert(A[i][j]);
                if (se.size() != 2) ok = false;
            }
            for (auto j : yoko) {
                set<char> se;
                for (auto i : tate) se.insert(A[i][j]);
                if (se.size() != 2) ok = false;
            }

            if (ok) {
                int c = __builtin_popcount(bit);
                int r = __builtin_popcount(bit2);
                mint add = part[c][r];
                res += add;
            }
        }
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

キーエンスプログラミングコンテスト 2020 F - Monochromization (5D, 銅色, 1100 点)