ABC121 D - XOR World
解法
「 について○○を計算した合計を求めよ」という問題で使える実装テクニックとして、代わりに「
について○○を計算した合計」から「
のうち○○を計算した合計」を引いたものを求めると考えると、変数が減る上に同じ処理を2回すれば良いだけになるので楽です。XORの場合は、引き算としてはXORをすればよいです。
そのため以降は のXORを考えます。このとき0から数えて、各ビットの値は以下のようになっています。
XORを求めたいので、重要なのは各ビットごとの1の個数の偶奇です。
図を見るとまず一番下以外のビットについては、隣り合う (偶数, 奇数) のペアではビット値が同じになっていることが分かります。つまり一番下以外の各ビットについて、このペアに含まれる1の個数は偶数個です。
一番下のビットだけはそうなっていませんが、隣り合う4つごとに区切って考えると1つの4つ組には1が2個あることが分かります。
つまり左から4つ組で区切っていくと、その4つの中では必ず全てのビットについて1の個数が偶数個になっている、つまり4つの数のXORがちょうど0になることが分かります。
そのため4つ組ができているところは無視してもよく、一番最後に余ったところだけを計算すればよいです。具体的には を含む4つ組の最初の数字は
になるので、この値から
までのXORを取ればよいです。
この計算を と
の両方に行い、その結果のXORを取ったものが答えです。
