/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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 である。
一般に 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
出力
答えを出力せよ。
入力例 1
2 2 10 30
出力例 1
40
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 となります。
入力例 2
4 10 0 0 0 0
出力例 2
0
入力例 3
11 998244353 314 159 265 358 979 323 846 264 338 327 950
出力例 3
236500026047
Score : 700 points
Problem Statement
You are given a sequence of N non-negative integers A=(A_1,A_2,\dots,A_N) and a positive integer K.
Find the bitwise \mathrm{XOR} of \displaystyle \sum_{i=1}^{K} A_{X_i} over all N^K sequences of K positive integer sequences X=(X_1,X_2,\dots,X_K) such that 1 \leq X_i \leq N\ (1\leq i \leq K).
What is bitwise \mathrm{XOR}?
The bitwise \mathrm{XOR} of non-negative integers A and B, A \oplus B, is defined as follows:
- When A \oplus B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if exactly one of the digits in that place of A and B is 1, and 0 otherwise.
Generally, the bitwise \mathrm{XOR} of k non-negative integers p_1, p_2, p_3, \dots, p_k is defined as (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k). We can prove that this value does not depend on the order of p_1, p_2, p_3, \dots, p_k.
Constraints
- 1 \leq N \leq 1000
- 1 \leq K \leq 10^{12}
- 0 \leq A_i \leq 1000
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N K A_1 A_2 \dots A_N
Output
Print the answer.
Sample Input 1
2 2 10 30
Sample Output 1
40
There are four sequences to consider: (X_1,X_2)=(1,1),(1,2),(2,1),(2,2), for which A_{X_1}+A_{X_2} is 20,40,40,60, respectively. Thus, the answer is 20 \oplus 40 \oplus 40 \oplus 60=40.
Sample Input 2
4 10 0 0 0 0
Sample Output 2
0
Sample Input 3
11 998244353 314 159 265 358 979 323 846 264 338 327 950
Sample Output 3
236500026047