AOJ1644 桂馬

問題

https://onlinejudge.u-aizu.ac.jp/problems/1644

マスのグリッドが与えられる。各マスは「.」か「#」である。「.」マスの部分集合であってそこに将棋の桂馬を置いたときに一手の移動でかぶらないような数を求めよ。解は巨大になり得るのでで求めよ。

制約

• 

解法

奇数行目のマスに置いた桂馬が偶数行のマスに影響を与えることは無い。また逆も然り。なので奇数行、偶数行で独立して解けば良い。サイズがの問題を二回解くことに帰着する。

奇数行目のみを考慮した場合の問題の解き方を考える。偶数行目のみを考慮した問題は全く同じ解き方になる。

わかりやすさのために、偶数行を全て削除して前に詰めたグリッドを考える。(行目 -> 行目, 行目 -> 行目....)

「.」マスに桂馬を置いたときの桂馬の攻撃できるマスに辺を張ったグラフを考える。このグラフ上の独立集合の数がわかれば良い。

連結成分を考えると、市松模様のグラフ上での独立集合の数を数え上げる問題を回解くことに帰着する。

この市松模様のグラフでは、各列に高々個の頂点しか無いため、こっからbitDPができる。

dpの計算は高速ゼータ変換を用いて高速化しよう

計算量はかな

実装

上記の計算量にさらにlogをつけた。まぁICPC国内なら良いでしょう。

#include <bits/stdc++.h>

constexpr long long MOD{1000000007};

long long mult(long long a, long long b) {
    return (a * b) % MOD;
}

long long add(long long a, long long b) {
    a += b;
    if (a >= MOD) a -= MOD;
    return a;
}

long long calc2(std::vector<std::vector<int>> A) {
    std::vector<long long> dp((1 << A[0].size()), 1);
    for (int i{1} ; i < (int)A.size() ; i++) {
        // dpをゼータ変換
        for (int j{} ; j < (int)A[i - 1].size() ; j++) {
            for (int bit{} ; bit < (int)(1 << A[i - 1].size()) ; bit++) {
                if (bit & (1 << j)) {
                    dp[bit] = add(dp[bit], dp[bit ^ (1 << j)]);
                }
            }
        }
        std::vector<long long> next((1 << A[i].size()));
        std::map<int, int> map;
        for (int j{} ; j < (int)A[i - 1].size() ; j++) {
            map[A[i - 1][j]] = j;
        }
        for (int bit{} ; bit < (int)(1 << A[i].size()) ; bit++) {
            std::vector<bool> ok(A[i - 1].size(), true);
            for (int j{} ; j < (int)A[i].size() ; j++) {
                if (!(bit & (1 << j))) continue;
                {
                    auto it{map.find(A[i][j] - 1)};
                    if (it != map.end()){
                        ok[it->second] = false;
                    }
                }
                {
                    auto it{map.find(A[i][j] + 1)};
                    if (it != map.end()){
                        ok[it->second] = false;
                    }
                }
            }
            int maximal{};
            for (int j{} ; j < (int)A[i - 1].size() ; j++) {
                if (ok[j]) maximal |= (1 << j);
            }
            next[bit] = dp[maximal];
        }
        dp = std::move(next);
    }
    long long res{};
    for (auto x : dp) res = add(res, x);
    return res;
}


long long calc(std::vector<std::string> S) {
    int M{(int)S[0].size()};
    std::vector<std::vector<int>> A(M), B(M);
    for (int i{} ; i < (int)S.size() ; i++) {
        for (int j{} ; j < (int)S[i].size() ; j++) {
            if (S[i][j] == '.') {
                if ((i + j) % 2) {
                    A[j].push_back(i);
                }
                else {
                    B[j].push_back(i);
                }
            }
        }
    }
    long long res{mult(calc2(A), calc2(B))};
    return res;
}

bool solve() {
    int N, M;
    std::cin >> N >> M;
    if (N == 0 and M == 0) {
        return false;
    }
    std::vector<std::string> S(N);
    for (auto& s : S) {
        std::cin >> s;
    }
    std::vector<std::string> odd, even;
    for (int i{} ; i < N ; i++) {
        if (i % 2) odd.push_back(S[i]);
        else even.push_back(S[i]);
    }
    long long ans{mult(calc(odd), calc(even))};
    std::cout << ans << '\n';
    return true;
}


int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    while (solve()) ;
}

感想

• スラスラ考察が終わって、実装も14分 -> 一発ACとかなり調子が良かった。
• 独立集合を数え上げる問題だとわかって、多項式時間で解く方法を探すことをすぐ捨てたのが良かった。
• この調子の良さをICPCで出したい。