(制限時間 4s.)
m <= 50 個のランプと、n <= 50 個のボタンがある。ボタン i は、いくつかのランプ S_i のオンオフを切り替える。ボタンの 2^n の押し方の組合せの中で、最大でいくつのランプを点灯させることができ、その方法は何通りあるか。
(まだ確かめてない)
まず S を掃き出す。掃き出したあとの行列は、左に単位行列があって、右に何かよくわからないものがあることになる。
ランクを r とする。自由度は、2^(n - r) あることになる。
r <= 27 と場合は、基底の組合せをすべて試せば良い。
r > 27 の場合は、右側のよくわからないのの幅は、22 以下になっている。この部分をキーとするDPを走らせれば良い。
