MUJIN 2018 H - タイル張り (1000 点)

コンテスト終了後に「もう少しで解けそうだったのに...」と言ったのんな。アレは嘘だった......

問題へのリンク

概要

H × W の盤面を白黒に塗り分ける方法のうち、白い部分を 1 × 2 の長方形のピースで隙間なく埋められるようなものは何通りあるか？
(998244353 で割ったあまりで)

制約

• 1 <= H <= 5
• 1 <= W <= 10⁹

考えたこと (前編)

一目見て

• H が小さい！2^H とかそれに類するものを状態に持って W 方向に進めていく DP っぽい
• そして W が大きい！これはきっと i 行目から i+1 行目への遷移の仕方は対称性から i に依らないことを活かして行列累乗に違いない

というところまでは思うん。さてさてさて...これがもし「ドミノの敷き詰め方」も含めた問題なら、つまりは

• 白黒の塗り方が予め与えられていて白い部分を敷き詰める方法が何通りあるか
• H × W の盤面上でドミノが互いに重ならないように置く方法が何通りあるか (置いた場所が白、置かなかった場所が黒になる)

という問題のいずれかであったならば、単純な行列累乗の問題である。どちらの問題であっても

• dp[ w ][ bit ] := w 列までをしきつめて、右側に bit で表される部分がはみ出すようなものの敷き詰め方の場合の数

という dp でよい。しかし今回の問題は「敷き詰め方」ではなく「塗り分け方」に関する問題である。敷き詰め方を気にする考察方法では恐らく通せない。というのも同じ塗り分け方でも、敷き詰め方が何通りもあるケースをなかなか上手く排除することができない。本番中は

塗り分けがあたえられたときに敷き詰め方が一通りになるようなルールを制定できないか？

という方向の考察をひたすらやっていて、その後もずっと考えたが徒労に終わってしまった。どんなルールを考案しても、闇のコーナーケースが次々と出現してしまう。。。根本的な発想の転換が必要だと悟った。。。

考えたこと (後編)

多分この発想の転換は非常に重要なので、今後のために認識しておくと良さそう。きっと過去に類題があるんじゃないかと思うので、後で SRM の過去問を漁ってみようと思う。

ある決まった白黒の塗り方が与えられたとき、ドミノの右側へのはみ出し方としてあり得るもののは 2^H 通りのうちの何通りか

という感じになる。そこで、2^2H 通りのそれぞれのはみ出し方 S について、

• dp[ w ][ S ] := w 列までの塗り分け方のうち、あり得るはみ出し方が S になるようなものの個数

という感じの DP をすればよい。これを行列累乗に持ち込む。しかしこのままでは、S は 2²⁵ = 2³² 通りあって間に合わない。しかし、様々な塗り分け方を考えたときあり得るはみ出し方としてあり得るものは、91 通りであることがわかる。

これにて無事に行列累乗ができる。

#include <iostream>
#include <map>
#include <vector>
using namespace std;

const long long MOD = 998244353;
long long mod(long long a, long long m) {
    return (a % m + m) % m;
}

template<class T> struct Matrix {
    vector<vector<T> > val;
    Matrix(int n = 1, int m = 1) {val.clear(); val.resize(n, vector<T>(m));}
    Matrix(int n, int m, T x) {val.clear(); val.resize(n, vector<T>(m, x));}
    void init(int n, int m, T x = 0) {val.clear(); val.resize(n, vector<T>(m, x));}
    void resize(int n, int m, T x = 0) {val.resize(n); for (int i = 0; i < n; ++i) val[i].resize(m, x);}
    int size() {return val.size();}
    inline vector<T>& operator [] (int i) {return val[i];}
    friend ostream& operator << (ostream& s, Matrix<T> M) {s << endl;
        for (int i = 0; i < M.val.size(); ++i) s << M[i] << endl; return s;}
};

template<class T> Matrix<T> operator * (Matrix<T> A, Matrix<T> B) {
    Matrix<T> R(A.size(), B[0].size());
    for (int i = 0; i < A.size(); ++i)
        for (int j = 0; j < B[0].size(); ++j)
            for (int k = 0; k < B.size(); ++k)
                R[i][j] = mod(R[i][j] + A[i][k] * B[k][j], MOD);
    return R;
}

template<class T> vector<T> operator * (Matrix<T> A, vector<T> B) {
    vector<T> v(A.size());
    for (int i = 0; i < A.size(); ++i)
        for (int k = 0; k < B.size(); ++k)
            v[i] = (v[i] + A[i][k] * B[k]) % MOD;
    return v;
}

template<class T> Matrix<T> pow(Matrix<T> A, long long n) {
    Matrix<T> R(A.size(), A.size());
    for (int i = 0; i < A.size(); ++i) R[i][i] = 1;
    while (n > 0) {
        if (n & 1) R = R * A;
        A = A * A;
        n >>= 1;
    }
    return R;
}

int H, W;

map<int,int> patterns;
map<pair<int,int>, int> step;

/* hamidashi + white-black of next line -> patterns of new hamidasis */
int nex(int hamidashi, int nextline) {
    int pattern = 0;
    if ((hamidashi & nextline) != hamidashi) return 0; // empty set
    nextline ^= hamidashi;
    for (int nexthamidashi = 0; nexthamidashi < (1<<H); ++nexthamidashi) {
        if ((nexthamidashi & nextline) != nexthamidashi) continue;
        
        // 左からはみ出されているわけでも、右にはみ出しているわけでもない部分が 2 マスずつ塗れるか
        int remline = nextline ^ nexthamidashi;
        int con = 0;
        bool ok = true;
        for (int i = 0; i < H; ++i) {
            if (remline & (1<<i)) ++con;
            else {
                if (con & 1) ok = false;
                con = 0;
            }
        }
        if (con & 1) ok = false;
        if (!ok) continue;
        
        pattern |= (1<<nexthamidashi);
    }
    return pattern;
}

/* enumerate all paterns */
void dfs(int p) {
    if (patterns.count(p)) return;
    int iter = (int)patterns.size();
    patterns[p] = iter;
    
    // enumerate white-black of nextline
    for (int nextline = 0; nextline < (1<<H); ++nextline) {
        int np = 0;
        for (int hamidashi = 0; hamidashi < (1<<H); ++hamidashi) {
            if (p & (1<<hamidashi)) {
                np |= nex(hamidashi, nextline);
            }
        }
        step[make_pair(p, np)]++;
        dfs(np);
    }
}

int main() {
    cin >> H >> W;
    patterns.clear(); step.clear();
    dfs(1); // only { no hamidasi }
    
    int n = (int)patterns.size();
    Matrix<long long> M(n, n, 0);
    for (map<int,int>::iterator i = patterns.begin(); i != patterns.end(); ++i) {
      for (map<int,int>::iterator j = patterns.begin(); j != patterns.end(); ++j) {
        M[i->second][j->second] = step[make_pair(j->first, i->first)];
      }
    }
    Matrix<long long> P = pow(M, W);
    vector<long long> ini(n, 0); ini[0] = 1;
    vector<long long> R = P*ini;
    long long res = 0;
    for (map<int,int>::iterator it = patterns.begin(); it != patterns.end(); ++it) {
        if (it->first & (1<<0)) res += R[it->second];
    }
    cout << res % MOD << endl;
}