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
ビット列を並べたものを行列だと考える
まず、区間に関する条件がないものとして考えます。
与えられた数列をビット列だと思って行列を構成します。
この行列の各行がそれぞれの要素に、各列がビットに対応します。ここから行をいくつか選んで要素のXOR和が のビット列と一致するような場合の数を求めるのが目的です。
今回の問題のように「要素のXOR和がある条件を満たすような、要素の選ぶ/選ばないの場合の数」を考える時、要素について「ある要素を他の要素にXORする」という操作を行っても答えは変わりません(こちらのE問題を参照)。これは行基本変形の1つであり、この操作を繰り返すことで行列を簡単にすることができます。上記の行列は以下の形まで簡単にできます。
この行列の特徴は、
全ての列(ビット桁)について、その桁が最上位ビットとなっているような行は高々1つである。
というものです。このように変形すると以下のような性質が成り立ちます。
行のXOR和がある値 に等しくなるような、行の選ぶ/選ばないの場合の数は、全要素が0である行の選び方を除くと高々1通りである。
具体的には値が大きい(最上位ビットが上である)行から順番に見ていきます。既に使うと決めた行のXOR合計を として、今見ている行の最上位ビットにおいてもし と の値が異なっていれば、この行を使うことでそのビット桁での と の値を一致させます。
このように行を選んでいって、最終的に選んだ行のビット列が全て と一致する場合はその1通りが条件を満たします。もし途中で と一致しないビットがある場合、どのように行の選び方を調整しても と同じビット列を得ることはできません。
つまり求めたい場合の数は、全要素が0であるような行の個数を として または になります。
区間に関する条件を考える
実際の問題では区間について「その区間から選ぶ要素の数は偶数個/奇数個である」という条件がありました。これの処理方法を考えます。
ここで、区間についての条件も行列に組み込んでしまうことを考えます。以下の図のように条件の個数 個だけ列を増やし、それぞれの列ではその区間に含まれる要素だけ1を立てます。
元々のビット列については、 のビット列と一致させることが必要でした。ではこの増やした列はどうなっているべきでしょうか?それぞれの列について、区間に含まれる要素を偶数個選んだ場合はXOR和は0、奇数個選んだ場合はXOR和は1になります。そのため与えられた条件の偶数個/奇数個に応じて、それぞれの列のXOR和を0/1にすることが条件を満たすことと同値になります。
こう考えてしまえば、前半で説明したものと解き方は同じです。条件の数だけ列を拡張し、「 のビット列と条件の偶数個/奇数個に対応するビット列を結合したもの」を新しい だと思って解けば同じ方法で解くことが出来ます。
実装は掃き出し法です。ビット列の長さを として 行 列の行列に掃き出し法を行うので、 を定数だと思うとこの解法の計算量は となります。
ACコード
#325219 (C++17(1z)) No.803 Very Limited Xor Subset - yukicoder