WhiteBlue

各列を $N$ ビットの整数で表す。ビット $0$ は白、ビット $1$ は青を表す。

まず、同じビットが縦に3つ連続しない列マスクだけを残す。その集合を $V$、要素数を $K$ とする。$N\le 8$ より $K\le 68$ である。各列で選ぶマスクは、あらかじめ塗られたマスの色とも一致する必要がある。

横方向の条件を確認するには直前の2列だけを記憶すればよい。$dp[a][b]$ を、処理済みの列の最後の2列が $a,b$ である有効な塗り方の数とする。新しい列 $c$ を追加する際、どの行でも $a,b,c$ の対応する3ビットがすべて同じでなければ追加できる。このとき に を加える。値はすべて で割った余りとして保持する。

$M=1$ の場合は、最初の列に置けるマスクの数を数える。それ以外の場合は、最初の2列の可能なマスクの組で DP を初期化し、3列目以降の遷移を行い、最後に全状態の値を足す。

縦方向に有効なマスクの生成は $O(N2^N)$ 時間、既存の色との整合性確認は $O(MNK)$ 時間、DP は $O(MK^3)$ 時間である。遷移を前計算する場合のメモリ使用量は である。加算する値は常に法で割った余りなので、符号付き32ビット整数に収まる。