#P13652. [ARC156D] Xor Sum 5

    ID: 12854 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-异或抵消对称性分析记忆化搜索奇偶性分析

[ARC156D] Xor Sum 5

题目描述

给定一个长度为 NN 的非负整数序列 A=(A1,A2,…,AN)A=(A_1,A_2,\dots,A_N),以及一个正整数 KK。

满足 1≤Xi≤N (1≤i≤K)1 \leq X_i \leq N\ (1\leq i \leq K) 的长度为 KK 的正整数序列 X=(X1,X2,…,XK)X=(X_1,X_2,\dots,X_K) 一共有 NKN^K 种。请你计算所有这些序列对应的 ∑i=1KAXi\displaystyle\sum_{i=1}^{K} A_{X_i} 的按位异或(bitwise XOR)。

按位异或(bitwise XOR)运算定义如下:对于非负整数 A,BA,B,A⊕BA \oplus B 表示 AA 和 BB 的二进制表示下,每一位 2k2^k(k≥0k \geq 0)的数,如果 A,BA,B 在该位上只有一个为 11,则结果为 11,否则为 00。

例如,3⊕5=63 \oplus 5 = 6(二进制表示为:011⊕101=110011 \oplus 101 = 110)。 一般地,kk 个非负整数 p1,p2,p3,…,pkp_1,p_2,p_3,\dots,p_k 的按位异或为 $(\dots((p_1 \oplus p_2) \oplus p_3)\oplus\dots\oplus p_k)$,并且可以证明其结果与顺序无关。

输入格式

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

NN KK A1A_1 A2A_2 …\dots ANA_N

输出格式

输出答案。

输入输出样例 #1

输入 #1

2 2
10 30

输出 #1

40

输入输出样例 #2

输入 #2

4 10
0 0 0 0

输出 #2

0

输入输出样例 #3

输入 #3

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

输出 #3

236500026047

说明/提示

限制条件

  • 1≤N≤10001 \leq N \leq 1000
  • 1≤K≤10121 \leq K \leq 10^{12}
  • 0≤Ai≤10000 \leq A_i \leq 1000
  • 所有输入均为整数

样例解释 1

XX 可能的取值为 (X1,X2)=(1,1),(1,2),(2,1),(2,2)(X_1,X_2)=(1,1),(1,2),(2,1),(2,2) 共 44 种,每种对应的 AX1+AX2A_{X_1}+A_{X_2} 分别为 20,40,40,6020,40,40,60。因此答案为 20⊕40⊕40⊕60=4020 \oplus 40 \oplus 40 \oplus 60=40。