/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 700 点
問題文
正整数 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 番目の品物を購入する。
高橋君が買った品物の値段の合計を求めてください。
\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) のビット単位 \mathrm{XOR} として定義されます。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
ビット単位 \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\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
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 のビット単位 \mathrm{XOR} である 61 が答えになります。
Score : 700 points
Problem Statement
You are given positive integers N,M and a sequence of positive integers A=(A_1,A_2,\ldots,A_N) of length N.
For a positive integer k, define f(k) as the answer to the following problem.
Takahashi has k yen. AtCoder Store has N items, and the i-th item costs A_i yen.
He performs the following action for i=1,2,\ldots,N in order.
- If the amount of money he currently has is at least A_i yen, he purchases the i-th item.
Find the total price of the items he purchased.
Find \displaystyle \bigoplus_{1\le k\le M} (k\times f(k)). Here, \displaystyle \bigoplus_{1\le k\le M} (k\times f(k)) is defined as the bitwise \mathrm{XOR} of 1\times f(1), 2\times f(2), \ldots, M\times f(M).
You are given T test cases; solve each of them.
What is bitwise \mathrm{XOR}?
The bitwise \mathrm{XOR} of non-negative integers A and B, A \oplus B, is defined as follows.
- In the binary representation of A \oplus B, the digit at the 2^k (k \geq 0) place is 1 if exactly one of the digits at the 2^k place in the binary representations of A and B is 1, and 0 otherwise.
In general, 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), and it can be proved that this does not depend on the order of p_1, p_2, p_3, \dots, p_k.
Constraints
- 1\le T \le 10
- 1\le N,M
- The sum of N over all test cases is at most 5\times 10^5.
- The sum of M over all test cases is at most 5\times 10^7.
- 1\le A_i \le M
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Each test case is given in the following format:
N M A_1 A_2 \ldots A_N
Output
Output the answers for the test cases in order, separated by newlines.
Sample Input 1
3 3 6 2 3 1 5 10 3 1 4 1 5 7 12 4 2 3 4 2 3 3
Sample Output 1
61 115 190
Consider the first test case.
For example, when Takahashi's initial amount of money is 3 yen, he acts as follows.
- For i=1: he has 3 yen, which is at least 2 yen, so he purchases the first item.
- For i=2: he has 1 yen, which is less than 3 yen, so he does not purchase the second item.
- For i=3: he has 1 yen, which is at least 1 yen, so he purchases the third item.
From this, we get f(3)=2+1=3.
The values of f(1),f(2),f(3),f(4),f(5),f(6) are 1,2,3,3,5,6, respectively. Thus, the answer is the bitwise \mathrm{XOR} of 1,4,9,12,25,36, which is 61.