マス目に書かれた Y の総数が奇数であれば，明らかに答えは \(0\) です． 以下では，この総数が偶数であるとし，その半分の値を \(y\) とします．

条件を満たすように柵を設置すると，各区画には Y が書かれたマスがちょうど \(2\) 個含まれているため，区画の数がちょうど \(y\) 個になっている必要があります． したがって，行間と列間に入れる柵の個数をそれぞれ \(h, w\) とすると，\((h+1)(w+1) = y\) が成り立ちます． すなわち，\(h + 1\) の値としてあり得るのは \(y\) の約数のみであり，そのうち

\[0 \le h < H,\ \ 0 \le w = \frac{y}{h+1} - 1 < W\]

を満たすものを全探索することを考えます．

上記の条件を満たす \((h, w)\) の組を \(1\) つ固定したとき，柵の設置場所の候補は本質的に一意に定まります． なぜなら，

• \(h\) 個の行間の柵だけを設置した状態で各区画がちょうど \(2(w+1)\) 個ずつの Y を含む必要があり，
• \(w\) 個の列間の柵だけを設置した状態で各区画がちょうど \(2(h+1)\) 個ずつの Y を含む必要があるからです．

ただし，X のみからなる行や列が存在する場合，その前後のどちらに柵を設置するかには任意性があり，この自由度（の総積）の分だけ条件を満たす柵の設置方法があるか，あるいは \(1\) つもないかのいずれかとなります．

Y の個数に関して，左上隅からの \(2\) 次元累積和を \(\mathrm{O}(HW)\) 時間で素朴に前計算しておきます． すると，行と列に関する必要条件を満たす柵の設置場所（と自由度）は \(\mathrm{O}(H + W)\) 時間で求まります． さらに，それらをともに満たす設置方法が見つかった場合，実際に柵を設置したときに元の条件（各区画に Y がちょうど \(2\) 個）を満たすかどうかは，\(\mathrm{O}(y)\) 時間で確認できます．

全探索の対象となる \((h, w)\) の組の個数を \(k\) としたとき，全体の計算量は \(\mathrm{O}(HW + k(H + W + y))\) となります． 制約の範囲内で \(k \le 80,\ ky \le 6.1 \times 10^7\) が成り立ち（あり得る \(y\) を全探索すれば確認できます），定数倍部分に重い処理も無いため，この見積りで実行時間制限に間に合います．

実装例