Educational Codeforces Round 48 (Rated for Div. 2) D. Vasya And The Matrix

問題概要

$n$ 要素の数列 $a$ と、 $m$ 要素の数列 $b$ が与えられます。
$n$ 行 $m$ 列の行列で、それぞれの行について、全要素のxorをとると $a$ に、それぞれの列について全要素のxorをとると $b$ になるようなものが存在するならば1つ求めてください。

解法

行う操作がxorなので、全要素を2進数の桁ごとに見て、最後に合算すればよいことがわかります。
ので、これ以降は $a,b$ が0,1からなる数列で、行列も0,1からなるものを求めることだけを考えればよいです。
構築できない条件を探してみます。
0,1からなるということと、xorが絡んでいることから、偶奇に着目します。
すると、数列 $a$ の総和と、 $b$ の総和の偶奇が異なる場合、構築できないことがわかります。
数列 $a$ の各値は、その行に存在している値の総和の偶奇と一致するように構築する必要があります。ということは、 $a$ の総和は、行列の要素全てに対する総和の偶奇と一致しているはずです。
このことは $b$ にも同様のことが言えます。
よって、行列全体の総和の偶奇は、 $a$ の総和の偶奇と一致していて、かつ、 $b$ の総和の偶奇と一致している必要があります。
ということで、 $a$ の総和と $b$ の総和の偶奇が一致しない場合には構築できないことがわかりました。
では、一致している場合には構築できるかどうか、を見ていきます。
わかりやすく、 $a$ の総和の偶奇で場合分けをします。

$a$ の総和、 $b$ の総和が奇数の場合
これはすごくシンプルで、 $(i,j)$ の値を決める場合、 $a_{i} = b_{j} = 1$ であれば1、それ以外なら0とすればよいです。
$a_{i},b_{j}$ の要素が1の際、その行(列)で1となっている要素の個数が奇数個になっている必要がありますが、 $a,b$ で1となっている要素の個数が奇数個であるため、上記のような構築をすればよいです。
$a$ の総和、 $b$ の総和が偶数の場合
この場合は少々厄介です。
単純な構築ができなかったため、どこかに値を押し付けて、最後に微調整を加えることを考えます。
すると、
$(1,b_{i})$ を、 $b_{i}$ と一致させる
$(a_{i},1)$ を、 $a_{i}$ と一致させる
とすると、 $a_{1},b_{1}$ 以外はうまく構築できます。
あとは最後に微調整をすればよく、 $(1,1)$ を $a_{1} \ xor \ b_{1}$ とすればよいです。

感想

こんな構築もあるみたいです。すごい。