数えるべきものは得られる可能性のあるマス目の状態数ですが、「\(HW\) マスの状態」を直接取り扱うのは困難です。そこで、適切な矩形領域との対応を考えます。

異なる矩形領域を選んだときに同一の状態が得られることがありますが、得られるマス目の状態を固定したとき、その状態を達成する最小の矩形領域を対応させます。ただし、操作をせずに得られる状態は別に加算するものとします。

よって、問題は以下のように言い換えられます。

矩形領域であって、上端の \(1\) 行、下端の \(1\) 行、左端の \(1\) 列、右端の \(1\) 列のすべてに \(1\) つ以上の白マスが存在するものの個数（に \(1\) を足したもの）を求めよ。

この言い換え後には、扱うデータが「\(HW\) マスの状態」から 「\(4\) つの整数（上下左右の端が何列目・何行目か）」になっており、解きやすい形になっています。

\(f_{i, j}\) を マス \((i, k)\) が白く塗られているような \(j\) 以上の最小の整数 \(k\)（存在しない場合は \(W + 1\)）、\(g_{i, j}\) をマス \((k, j)\) が白く塗られているような \(i\) 以上の最小の整数 \(k\)（存在しない場合は \(H + 1\)）とします。

左端の列を \(l\) 列目、右端の列を \(r\) 列目と決め打った状態を考えます。

上端の行を \(u\) 行目、下端の行を \(d\) 行目としたとき、この矩形領域が条件を満たすことは \(f_{u, l} \leq r, f_{d, l} \leq r, g_{u, l} \leq d, g_{u, r} \leq d\) を満たすことと同値です。

長さ \(H\) の数列 \(A\) を \(f_{i, l} \leq r\) のとき \(A_i = 1\)、そうでないとき \(A_i = 0\) で定めると、\(f_{u, l} \leq r\) を満たすような \(u\) を取ったときに条件を満たす \(d\) の個数は \(\displaystyle\sum_{i = \max(g_{u, l}, g_{u, r})}^{H}A_i\) となり、あらかじめ \(A\) の累積和を取っておくことで \((l, r)\) ごとに条件を満たす矩形領域の個数を \(O(H)\) 時間で数えられます。

以上より、この問題は \(O(HW^2)\) 時間で解くことができます。与えられたマス目の行と列を入れ替えることで \(O(H^2W)\) 時間でも解くことができるので \(H, W\) の大小に応じてこれらを使い分けることで \(O(HW \min(H, W))\) 時間で解くことができ、これは適切な実装のもと十分高速です。