みんなのプロコン2019予選 E - Odd Subrectangles

Page content

問題概要

和が偶数になるものを全体から引くことを考える.
列の部分集合を決めたとき、和が偶数になるような行の部分集合の決め方は以下のようになる.
- 全行の和が偶数: $2^{N}$通り
- ある行の和が奇数: $2^{N-1}$通り
よって、全行の和が偶数になるような列の部分集合の個数が数えられればOK.
以下、$\mathbf{F}_{2}$で考える.
列の部分集合を選ぶ -> 入力の行列$A$に0, 1からなる$M$成分のベクトル$x$を作用させる, と対応させる.
このとき、全行の和が偶数ということは、 $$Ax = 0$$ が成立するということである.
言い換えると、$x$が線形変換$A$の$Ker$に含まれていれば良く、$Ker$の要素数を数える問題に帰着される.
行列$A$のrankを$r$とすると、$A$を標準形にしたときに、前の$r$成分は必ず0でなくてはならない. 逆にその他の成分は任意に決められる.
よって全行の和が偶数であるものの個数は$2^{M-r}$個である.
最終的な答えは, $$ans = 2^{N+M} - (2^{M-r} * 2^{N} + (2^{M} - 2^{M-r}) * 2^{N-1})$$ となる.