[ARC156D] Xor Sum 5

ID: 1672

Type: RemoteJudge

2000ms

1024MiB

Tried: 0

Accepted: 0

Difficulty: (None)

Uploaded By:

jike1994

配点 : $700$ 点

問題文

長さ $N$ の非負整数列 $A=(A_1,A_2,\dots,A_N)$ 、および正整数 $K$ が与えられます。

$1 \leq X_i \leq N\ (1\leq i \leq K)$ を満たす長さ $K$ の正整数列 $X=(X_1,X_2,\dots,X_K)$ は $N^K$ 通り考えられますが、それらすべてに対する $\displaystyle \sum_{i=1}^{K} A_{X_i}$ のビット単位 $\mathrm{XOR}$ を求めてください。

ビット単位 $\mathrm{XOR}$ 演算とは

非負整数 $A, B$ のビット単位 $\mathrm{XOR}$ 、 $A \oplus B$ は、以下のように定義されます。

$A \oplus B$ を二進表記した際の $2^k$ ( $k \geq 0$ ) の位の数は、 $A, B$ を二進表記した際の $2^k$ の位の数のうち一方のみが $1$ であれば $1$ 、そうでなければ $0$ である。

例えば、3 \oplus 5 = 6 となります (二進表記すると: 011 \oplus 101 = 110)。
一般に k 個の非負整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{XOR} は (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k) と定義され、これは p_1, p_2, p_3, \dots, p_k の順番によらないことが証明できます。

制約

$1 \leq N \leq 1000$
$1 \leq K \leq 10^{12}$
$0 \leq A_i \leq 1000$
与えられる入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$N$ $K$

$A_1$ $A_2$ $\dots$ $A_N$

出力

答えを出力せよ。

Sample Input 1

2 2
10 30

Sample Output 1

$X$ として考えられるのは $(X_1,X_2)=(1,1),(1,2),(2,1),(2,2)$ の $4$ 通りであり、それぞれに対する $A_{X_1}+A_{X_2}$ は $20,40,40,60$ です。よって答えは $20 \oplus 40 \oplus 40 \oplus 60=40$ となります。

Sample Input 2

4 10
0 0 0 0

Sample Output 2

Sample Input 3

11 998244353
314 159 265 358 979 323 846 264 338 327 950

Sample Output 3

236500026047

#ARC156D. [ARC156D] Xor Sum 5

問題文

制約

入力

出力

Status

Development

Support