「みんなのプロコン 2019」-E Odd Subrectangles 解説

問題リンク

解説

DP などを考えても解けそうにない。

行基本変形に思いを馳せる。$N \geq M $ を仮定して、掃き出し法を行ってみる。この行列の rank を $R$ とする。 処理後の行列を眺めると、$R$ 次正方行列についてこの問題を解いて、それに $2^{N+M-2R}$ をかければ答えとなることがわかる。 計算量に余裕があるので、正方行列について解くには、次の式を用いるといい。これは、正方行列においては、選んだ行と列の和集合のサイズに subrectangle の値の和が等しいことを考えると出てくる。

$$ \sum_{i\&1=1,1\leq i\leq R}\binom{R}{i}\sum_{j=0}^{R-i}\binom{R-i}{j}2^{R-i-j} $$

掃き出し法にかかる $O(N^2M)$ が時間計算量のボトルネックとなる。