← 返回题目列表

AtCoder · arc217_d

D. 贪婪的顾客

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

给你正整数 N,M 和正整数序列 A=(A_1,A_2,\ldots,A_N) 长度 N.

对于正整数 k,定义 f(k) 作为以下问题的答案。

高桥有 k 日元。 AtCoder 商店有 N 项目,以及 i第一项成本 A_i 日元。

他执行以下操作 i=1,2,\ldots,N 按顺序。

  • 如果他目前拥有的金额至少为 A_i 日元,他购买了 i- 第一项。

查找他购买的商品的总价。

查找 \displaystyle \bigoplus_{1\le k\le M} (k\times f(k))。在这里, 交换后 \displaystyle \bigoplus_{1\le k\le M} (k\times f(k)) 定义为按位 \mathrm{XOR} of 1\times f(1), 2\times f(2), \ldots, M\times f(M).

你被给予 T 测试用例;解决它们中的每一个。

什么是按位 \mathrm{XOR}?

按位 \mathrm{XOR} 非负整数 A 和 B, A \oplus B定义如下。

  • 在二进制表示中 A \oplus B,位于的数字 2^k (k \geq 0) 地方是 1 如果恰好是位于的数字之一 2^k 放置在二进制表示中 A 和 B is 1,和 0 否则。
例如, 3 \oplus 5 = 6 (二进制: 011 \oplus 101 = 110).
一般来说,按位 \mathrm{XOR} of k 非负整数 p_1, p_2, p_3, \dots, p_k 定义为 (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k),并且可以证明这不依赖于顺序 p_1, p_2, p_3, \dots, p_k.

约束

  • 1\le T \le 10
  • 1\le N,M
  • 总和 N 所有测试用例最多 5\times 10^5.
  • 总和 M 所有测试用例最多 5\times 10^7.
  • 1\le A_i \le M
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

每个测试用例均按以下格式给出:

N M
A_1 A_2 \ldots A_N

输出

按顺序输出测试用例的答案,以换行符分隔。


示例输入 1

3
3 6
2 3 1
5 10
3 1 4 1 5
7 12
4 2 3 4 2 3 3

示例输出 1

61
115
190

考虑第一个测试用例。

例如,当高桥的初始金额为 3 日元,他的行为如下。

  • 对于 i=1:他有 3 日元,至少 2 日元,所以他购买了第一个商品。
  • 对于 i=2:他有 1 日元,小于 3 日元,所以他没有购买第二件商品。
  • 对于 i=3:他有 1 日元,至少 1 日元,所以他购买了第三件商品。

由此,我们得到 f(3)=2+1=3.

的值 分别是 f(1),f(2),f(3),f(4),f(5),f(6) 是 1,2,3,3,5,6。因此,答案是按位 \mathrm{XOR} of 1,4,9,12,25,36,即 61.