時間計算量 \(O(N)\) の解法を解説します。 \(r _ k\) を \(R\) に \(k\) が出現する回数とし、同様に \(c _ k\) も定義します。 \(r _ 1 + 2 r _ 2 \neq c _ 1 + 2 c _ 2\) ならば答えは \(0\) です。 以降、\(M \coloneqq r _ 1 + 2 r _ 2 = c _ 1 + 2 c _ 2\) とします。

まず、\(R _ i = 0\) である行 \(i\) や \(C _ j = 0\) である列 \(j\) は常に \(0\) ですので、削除してしまいます。 次に、\(R _ i = 2\) である行 \(i\) を \(2\) つに分裂させます。同様に、\(C _ j = 2\) である列 \(j\) も \(2\) つに分裂させます。 一連の操作で \(M \times M\) の大きさになった行列に、どの行や列の和も \(1\) になるように \(0\) と \(1\) を書き込むことを考えましょう。 書き込んだのち、\(2\) つに分裂した行や列を足し合わせるように元に戻すと、元の和の条件を満たす答えが得られていることが分かります。

分裂を元に戻す操作は複数の行列から同じ行列を生成するので、この分を上手く数える必要があります。 正確には、条件を満たす \(M \times M\) 行列を、元は同じ行だった \(2\) つの行の入れ替えや同様の列の入れ替えで一致するものを同一視して数え上げます。 Burnside の補題より、\(\displaystyle 2 ^ {r _ 2 + c _ 2}\) 通りの操作のそれぞれについて、変化しない行列の個数を数えて足し合わせれば良いです。 入れ替える行の個数と入れ替える列の個数が一致していない場合、変化しない行列は \(0\) 個です。 従って、各 \(0 \leq k \leq \min(r _ 2, c _ 2)\) について、行の組 \(k\) 個と列の組 \(k\) 個を選んでそれらを入れ替えた場合に不変な行列を数えます。 これは以下の式で与えられます。

\[ \binom{r _ 2}{k} \binom{c _ 2}{k} k! 2 ^ k (M - 2k)! \]

なお、「\(2\) が丁度 \(x\) 個書き込まれるような解の個数」から「\(y\) カ所を \(2\) に固定して、残りを分裂させた場合の解の個数」を求める式を立て、その関係を逆転させる包除原理風の方法でも同じ式が得られます。