Colorful Domino Tiling

小さい入力：配置と色付けの全探索

$NM$ が奇数なら答えは零である。それ以外では、まだ覆われていない最初のマスを右または下のマスと組にする探索で、すべての敷き詰め方を一度ずつ列挙できる。各配置について、ドミノを頂点、隣接関係を辺とするグラフを作る。

頂点を順に色付けする。使用済みの色が $c$ 種類なら、既存の色のうち隣接する先行頂点と衝突しないものを試し、さらに新しい色を代表一色で試して $K-c$ 倍する。これは初登場順による色名の正規化である。サブタスク 1 ではドミノ数は最大八個である。ドミノ数 $D$、配置数 $L$ に対し、保守的な上界は時間 $O(LD^2B_D)$、空間 $O(NM+D^2)$ である。$B_D$ は Bell 数を表す。

全体の解法：境界 DP

必要なら格子を回転し、幅を $W=\min(N,M)$、高さを $H=\max(N,M)$ とする。上から下へ、各行では左から右へ一マスずつ処理する。各列で最後に処理したマスを境界に保持する。処理直前の同じ列の要素は上の隣接マスであり、現在行で直前に処理した要素は左の隣接マスである。

境界の各マスには、正規化した色番号と、既に処理したマスとのペアが完成しているかを表すビットを保存する。存在しないマスの色番号は零とする。未完成のマスも色は決まっているが、後で右または下のマスと組になる必要がある。境界から消えるマスは未処理マスと隣接しないので、その色を別途記憶する必要はない。

境界を左から読んで色の初登場順に $1,2,3,\ldots$ を付ける。例えば $(7,2,7,5)$ は $(1,2,1,3)$ となる。DP 値は、その状態に対応する実際の色付き配置の数である。

遷移

新しいマスの上と左の隣接マスを $U,L$ とする。存在しない隣接マスは無視する。

• $U$ が未完成なら、今のマスと必ず組にする。色は $U$ と同じで、新しいマスは完成済みとなる。$L$ があればその色とは異なる必要がある。$U$ を境界から取り除く。
• $U$ が存在しないか完成済みなら、未完成の $L$ と組にできる。$$ と同じ色にし、 があればその色とは異なることを確認する。 と新しいマスを両方完成済みにする。

最後の選択では、現在の境界に $c$ 色あれば既存の各色を試す。境界にない色は同じ新番号になるので、一つの遷移にまとめて $K-c$ 倍する。過去に使ったが境界から消えた色もこの選択肢に含まれる。過去に使った色の総数ではなく、現在の境界の色数を数える。

上の要素を新しいマスに置き換え、再び正規化する。初期状態は空の境界で値は一。全マスの処理後、境界の全マスが完成済みの状態だけを足す。

正当性

各ドミノは行優先順で二番目のマスを処理するときに一度だけ完成する。上の未完成マスは今組にしなければ後で相手を得られないため、最初の遷移は強制される。それ以外では左と組にするか将来の相手を待つかの二択がすべての可能性を分割する。新しいマスの処理済み隣接マスは上と左だけなので、すべての隣接条件を正確に確認できる。色名の変更で実現可能性は変わらず、新しい色の $K-c$ 倍で実際の色名の選択数を復元する。よって各合法な色付き配置を重複なく数える。

状態数と計算量

色の同値関係は集合分割であり、その数は Bell 数 $B_W$ 以下、$B_8=4140$ である。完成ビットを含めると $B_W2^W$ 状態以下となる。四本の縦ドミノの色を とすることが可能なので、色の同値関係は非交差とは限らない。この DP を Catalan 数で制限したり、交差する色パターンを除去したりしてはいけない。

一状態当たり色の選択が $O(W)$ 個、正規化が $O(W)$ かかる。ハッシュ操作が平均定数時間なら、時間は $O(HW\cdot B_W2^W\cdot W^2)$、追加空間は である。到達可能な状態だけを保持し、この実装の最大入力では一段階につき約 状態となる。

各演算後に $P=998\,244\,353$ で剰余を取る。積は $100(P-1)$ 以下、和は $2(P-1)$ 以下である。圧縮状態は 40 ビット以内で、符号付き 64 ビット整数で十分である。独立検証用実装では異色条件を包除原理で展開し、連結成分を保持して計算する。

Solution written by GPT6