AT_arc217_d [ARC217D] Greedy Customer

给定正整数 $N, M$，还有一个长度为 $N$ 的正整数序列 $A = (A_1, A_2, \ldots, A_N)$。 对于正整数 $k$，定义 $f(k)$ 为如下过程的答案： > 高桥有 $k$ 日元。AtCoder 商店有 $N$ 件商品，第 $i$ 件商品的价格为 $A_i$ 日元。 > > 他依次对 $i=1,2,\ldots,N$ 执行以下操作。 > > - 如果他当前持有的金额不小于 $A_i$ 日元，他就购买第 $i$ 件商品，并支付 $A_i$ 日元。 > > 求他购买到的商品的总价格。 请计算 $\displaystyle \bigoplus_{1\le k\le M} (k\times f(k))$。这里，$\displaystyle \bigoplus_{1\le k\le M} (k\times f(k))$ 表示 $1\times f(1), 2\times f(2), \ldots, M\times f(M)$ 的按位异或（bitwise XOR）。 有 $T$ 组测试数据，请分别输出答案。 什么是按位异或？对于非负整数 $A$ 和 $B$，$A \oplus B$ 的定义如下： - 若 $A$ 和 $B$ 的二进制表达下，某一位只有一个为 $1$，则 $A \oplus B$ 的该位为 $1$；否则为 $0$。 例如，$3 \oplus 5 = 6$（用二进制表示为：$011 \oplus 101 = 110$）。 一般来说，$k$ 个非负整数 $p_1, p_2, \ldots, p_k$ 的按位异或为 $(\ldots ((p_1 \oplus p_2) \oplus p_3) \oplus \ldots \oplus p_k)$，且可以证明异或顺序不影响结果。

输入按以下格式给出： > $T$ > $\text{case}_1$ > $\text{case}_2$ > $\vdots$ > $\text{case}_T$ 每组测试数据格式如下： > $N$ $M$ > $A_1$ $A_2$ $\ldots$ $A_N$

按输入顺序为每组测试数据输出答案，每个答案一行。

### 样例解释 1 考虑第一组测试数据。 例如，当高桥初始金额为 $3$ 日元时，其操作如下： - $i=1$ 时：手中有 $3$ 日元，不少于 $2$ 日元，购入第 1 件商品。 - $i=2$ 时：剩余 $1$ 日元，少于 $3$ 日元，无法购买第 2 件商品。 - $i=3$ 时：剩余 $1$ 日元，不少于 $1$ 日元，购入第 3 件商品。 由此可得 $f(3)=2+1=3$。 各 $f(1),f(2),f(3),f(4),f(5),f(6)$ 分别为 $1,2,3,3,5,6$。 所以答案为 $1,4,9,12,25,36$ 的按位异或，结果是 $61$。 ### 数据范围 - $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$ - 所有输入均为整数。 由 ChatGPT 5 翻译