XOR について完全理解することが求められる...!
問題概要
を偶数とする。 個の 0 以上の整数 であって、以下の条件を満たすものを求めよ。
- 個の整数のうち 番目を除外した 個の整数の XOR 和が となる
制約
考えたこと
が偶数というのが不気味だけど、とりあえず の場合について考えてみる。このとき、条件は次のような方程式になる。ただし、XOR を「 ^ 」で表している。
x2 ^ x3 ^ x4 = A1 x1 ^ x3 ^ x4 = A2 x1 ^ x2 ^ x4 = A3 x1 ^ x2 ^ x3 = A4
こういう対称な方程式を見たら、とりあえず式全部を足してみたくなる!全部足すと、左辺は、
- x1 が 3 個
- x2 が 3 個
- x3 が 3 個
- x4 が 3 個
という感じになっている。ここで、XOR 和の性質を思い出そう。XOR 和は、以下のように、偶数個だと 0 になり、奇数個だと 1 個分になる、という性質がある。
- a ^ a = 0
- a ^ a ^ a = a
- a ^ a ^ a ^ a = 0
- a ^ a ^ a ^ a ^ a = a
- ...
よって、上の連立方程式を式を全部足すと、次のようになる。
x1 ^ x2 ^ x3 ^ x4 = B
(ただし B = A1 ^ A2 ^ A3 ^ A4 とした)
ここまで来たら
とても嬉しいことに、x1, x2, x3, x4 の XOR 和がわかったので、ノリとしては
- x1 ^ x2 ^ x3 ^ x4 = B
から
- x2 ^ x3 ^ x4 = A1
を "引く" というのをすると、x1 を求めることができそうな気がしてくる (同様に、x2, x3, x4 も求められる)。「引く」という行為が実現えきればよいことになるので、XOR 和において「引く」とはどういうことだろう...と疑問が湧いてくる。でも実は、XOR 和においては、「足す」も「引く」も一緒なのだ。試しに、
- x1 ^ x2 ^ x3 ^ x4 = B
- x2 ^ x3 ^ x4 = A1
を足してみよう。そうすると、x1 以外の x2, x3, x4 はそれぞれ 2 個ずつの XOR 和になるので、0 になって消えるのだ。よって、
- x1 = B ^ A1
となる。これで x1 が求められた。同様にして、
- x1 = B ^ A1
- x2 = B ^ A2
- x3 = B ^ A3
- x4 = B ^ A4
になるということもわかる。
一般の N でも
ここまで N = 4 で考えていたけど、一般の N でも一緒で
- B = A1 ^ A2 ^ ... ^ AN として
- x[ i ] = B ^ Ai
で求められる。計算量は 。なお、「N が偶数」という条件がどこに響いてくるのかについては、下の方で補足を。
#include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; vector<long long> A(N); long long B = 0; for (int i = 0; i < N; ++i) { cin >> A[i]; B ^= A[i]; } for (int i = 0; i < N; ++i) cout << (B^A[i]) << endl; }
おまけ: N が奇数だと...??
N = 4 のときの連立方程式は
x2 ^ x3 ^ x4 = A1 x1 ^ x3 ^ x4 = A2 x1 ^ x2 ^ x4 = A3 x1 ^ x2 ^ x3 = A4
という形だった。これを全部足すとき、x1, x2, x3, x4 がそれぞれ 3 個ある。これは一般には N-1 個ということになる。よって
- N が偶数だと、N - 1 は奇数なので、xi がそれぞれ奇数個なので、 XOR 和すると xi になる
- N が奇数だと、N - 1 は偶数なので、xi がそれぞれ偶数個なので、XOR 和をとると 0 になる
という風になる。N が奇数だと、各式を全部足したときに左辺が 0 になってしまうのだ。