B - Three Coins
問題文
彩国には、 $N$ 種類の硬貨があります。
種類 $i$ の硬貨には、 $A_i$ 円の価値があります。
彩大くんは、これらの硬貨からちょうど $3$ 枚選び、価値の合計を求めます。
なお、同じ硬貨を複数回選んでも構いません。
あり得る「選んだ価値の合計」の値すべてについて、 XOR をとった結果を求めてください。
より形式的には、集合 $S$ を $S = \{ X_1, X_2, \ldots, X_M \} = \{ A_i + A_j + A_k \mid 1 \le i \le j \le k \le N \}$ と定めます。
このとき、 $S$ のすべての要素について XOR をとった結果、すなわち $X_1 \oplus X_2 \oplus \ldots \oplus X_M$ を求めてください。
ただし、 $\oplus$ は XOR を表します。
XOR とは？
整数 $a, b$ の XOR $a \oplus b$ は、以下のように定義されます。- $a \oplus b$ を二進表記した際の $2^k (k \ge 0)$ の位の数は、$a, b$ を二進表記した際の $2^k$ の位の数のうち一方のみが $1$ であれば $1$ 、そうでなければ $0$ である。
例えば、 $3 \oplus 5 = 6$ となります (二進表記すると: $011 \oplus 101=110$) 。
なお、この演算において、計算する順序によらず求める値は一意に定まります。
制約
- $1 \le N \le 2 \times 10^5$
- $1 \le A_i \le 10^{16}$
- $A_{i+1}$ は $A_i$ の倍数 ($1 \le i \le N-1$)
- 入力はすべて整数である
部分点
この問題はいくつかの小課題に分けられ、その小課題の全てのテストケースに正解した場合に、「この小課題に正解した」とみなされます。
提出したソースコードの得点は、正解した小課題の点数の合計となります。
- (10 点) $N \le 200$
- (90 点) 追加の制約はない。
入力
入力は以下の形式で標準入力から与えられる。
$A_1$ $A_2$ $...$ $A_N$
出力
とり得る「選んだ価値の合計」の値すべてについて、 XOR をとった結果を 1 行で出力せよ。
3
1 5 10
26
集合 $S$ の要素は、以下の 10 個です。
同じ硬貨を複数回選んでもよいことに注意してください。
- $1 + 1 + 1 = 3$
- $1 + 1 + 5 = 7$
- $1 + 1 + 10 = 12$
- $1 + 5 + 5 = 11$
- $1 + 5 + 10 = 16$
- $1 + 10 + 10 = 21$
- $5 + 5 + 5 = 15$
- $5 + 5 + 10 = 20$
- $5 + 10 + 10 = 25$
- $10 + 10 + 10 = 30$
これらの値の排他的論理和をとると、 $3 \oplus 7 \oplus 12 \oplus 11 \oplus 16 \oplus 21 \oplus 15 \oplus 20 \oplus 25 \oplus 30 = 26$ となります。
なお、この入力例は小課題 1, 2 の制約を満たします。
3
1 1 1
3
集合 $S$ の要素は $3$ のみです。
重複する要素がある場合は、その要素を 1 回だけ数えることに注意してください。
なお、この入力例は小課題 1, 2 の制約を満たします。