AT_arc156_d.[ARC156D] Xor Sum 5

给定一个长度为 $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}$ 的按位异或（bitwise XOR）。

按位异或（bitwise XOR）运算定义如下：对于非负整数 $A,B$，$A \oplus B$ 表示 $A$ 和 $B$ 的二进制表示下，每一位 $2^k$（$k \geq 0$）的数，如果 $A,B$ 在该位上只有一个为 $1$，则结果为 $1$，否则为 $0$。

例如，$3 \oplus 5 = 6$（二进制表示为：$011 \oplus 101 = 110$）。
一般地，$k$ 个非负整数 $p_1,p_2,p_3,\dots,p_k$ 的按位异或为 $(\dots((p_1 \oplus p_2) \oplus p_3)\oplus\dots\oplus p_k)$，并且可以证明其结果与顺序无关。

输入以如下格式从标准输入读入：

$N$ $K$ $A_1$ $A_2$ $\dots$ $A_N$

输出答案。

限制条件

• $1 \leq N \leq 1000$
• $1 \leq K \leq 10^{12}$
• $0 \leq A_i \leq 1000$
• 所有输入均为整数

样例解释 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$。

由 ChatGPT 4.1 翻译