ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

yukicoder No.803 Very Limited Xor Subset

No.803 Very Limited Xor Subset - yukicoder

解法

AtCoderに「Limited Xor Subset」という問題があります。この問題の想定解法は今回のyukicoderの問題とは全く違うものですが、この問題に対するこちらの別解がとても参考になります。私もコンテスト本番はこの記事を見て解法を編み出しました。

Code Thanks Festival 2017 F Limited Xor Subset 解説 | 東京工業大学デジタル創作同好会traP

ビット列を並べたものを行列だと考える

まず、区間に関する条件がないものとして考えます。

与えられた数列をビット列だと思って行列を構成します。

f:id:betrue12:20190318002330p:plain

この行列の各行がそれぞれの要素に、各列がビットに対応します。ここから行をいくつか選んで要素のXOR和が  X のビット列と一致するような場合の数を求めるのが目的です。

今回の問題のように「要素のXOR和がある条件を満たすような、要素の選ぶ/選ばないの場合の数」を考える時、要素について「ある要素を他の要素にXORする」という操作を行っても答えは変わりません(こちらのE問題を参照)。これは行基本変形の1つであり、この操作を繰り返すことで行列を簡単にすることができます。上記の行列は以下の形まで簡単にできます。

f:id:betrue12:20190318002341p:plain

この行列の特徴は、

全ての列(ビット桁)について、その桁が最上位ビットとなっているような行は高々1つである。

というものです。このように変形すると以下のような性質が成り立ちます。

行のXOR和がある値  X に等しくなるような、行の選ぶ/選ばないの場合の数は、全要素が0である行の選び方を除くと高々1通りである。

具体的には値が大きい(最上位ビットが上である)行から順番に見ていきます。既に使うと決めた行のXOR合計を  s として、今見ている行の最上位ビットにおいてもし  s X の値が異なっていれば、この行を使うことでそのビット桁での  s X の値を一致させます。

このように行を選んでいって、最終的に選んだ行のビット列が全て  X と一致する場合はその1通りが条件を満たします。もし途中で  X と一致しないビットがある場合、どのように行の選び方を調整しても  X と同じビット列を得ることはできません。

つまり求めたい場合の数は、全要素が0であるような行の個数を  z として  2^{z} または  0 になります。

区間に関する条件を考える

実際の問題では区間について「その区間から選ぶ要素の数は偶数個/奇数個である」という条件がありました。これの処理方法を考えます。

ここで、区間についての条件も行列に組み込んでしまうことを考えます。以下の図のように条件の個数  M 個だけ列を増やし、それぞれの列ではその区間に含まれる要素だけ1を立てます。

f:id:betrue12:20190318004053p:plain

元々のビット列については、 X のビット列と一致させることが必要でした。ではこの増やした列はどうなっているべきでしょうか?それぞれの列について、区間に含まれる要素を偶数個選んだ場合はXOR和は0、奇数個選んだ場合はXOR和は1になります。そのため与えられた条件の偶数個/奇数個に応じて、それぞれの列のXOR和を0/1にすることが条件を満たすことと同値になります。

こう考えてしまえば、前半で説明したものと解き方は同じです。条件の数だけ列を拡張し、「 X のビット列と条件の偶数個/奇数個に対応するビット列を結合したもの」を新しい  X だと思って解けば同じ方法で解くことが出来ます。

実装は掃き出し法です。ビット列の長さを  B = 30 として  N B+M 列の行列に掃き出し法を行うので、 B を定数だと思うとこの解法の計算量は  O(NM^{2}) となります。

ACコード

#325219 (C++17(1z)) No.803 Very Limited Xor Subset - yukicoder