D - 数列 XOR Editorial by ngtkana
\(a\) と \(b\) の張る \(\mathbf F _ 2 ^ {60}\) の部分空間が等しいかどうかを判定すればよいまでは OK であるとして、その楽な方法のひとつをご説明します。
\(a\) の張る空間が \(b\) の張る空間を含むかどうかを判定できれば、これを \(a\) と \(b\) を入れ替えてもう一度判定することで目的が達成されますね。\(a, b\) の各項を \(2\) 進展開してそれぞれ縦に書いて、それを横にならべて \(60 \times 2n\) 行列を作ります。これを行基本変形で掃き出したときに、\(b\) 側にピボットがひとつでもあればアウト、そうでなければ OK です。
posted:
last update: