Hatena::Grouptopcoder

解いた問題

TopCoder: OgieKako / Codeforces: OgieKako

 | 

2017-01-13SRM 705 - 1000

解答

02:49

(まだ確かめてない)

まず S を掃き出す。掃き出したあとの行列は、左に単位行列があって、右に何かよくわからないものがあることになる。

ランクを r とする。自由度は、2^(n - r) あることになる。

r <= 27 と場合は、基底の組合せをすべて試せば良い。

r > 27 の場合は、右側のよくわからないのの幅は、22 以下になっている。この部分をキーとするDPを走らせれば良い。

 |