AtCoder Regular Contest 217 A,B,C,D問題メモ

AtCoder Regular Contest 217

A - Min of Sum of XOR

• 正整数 $N$ が与えられます。
• $(1,2,\ldots,N)$ の順列 $P=(P_1,P_2,\ldots,P_N)$ であって、 $\displaystyle \sum_{i=1}^N \bigoplus_{1\le j\le i} P_j$ を最小化するものを一つ求めてください。
• ただし、 $\displaystyle \bigoplus_{1\le j\le i} P_j$ は $P_1,P_2,\ldots,P_i$ のビット単位 $\mathrm{XOR}$ として定義されます。
• $T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

• $1\le T\le 10^3$
• $1\le N$
• 全てのテストケースにおける $N$ の総和は $2\times 10^5$ 以下
• 入力される値は全て整数

実験あるべし。$O(N!)$ の愚直解を書いて調べれば、

N   最小値を与えるP（のうち辞書順最小のもの）
3   1 3 2
4   1 3 2 4
5   1 3 2 4 5
6   1 3 2 4 5 6
7   1 3 2 4 5 7 6
8   1 3 2 4 5 7 6 8
...

なので、2番目と3番目、6番目と7番目、、、$4k+2$ 番目と $4k+3$ 番目が入れ替わったものが最適と推測できる。

Python3

def naive(n):
    from itertools import permutations
    ans = 1 << 60
    best = ()
    for ppp in permutations(range(1, n + 1)):
        result = 0
        tmp = 0
        for p in ppp:
            tmp ^= p
            result += tmp
        if ans > result:
            ans = result
            best = ppp
    return ans, best


def check():
    print(naive(3))
    print(naive(4))
    print(naive(5))
    print(naive(6))
    print(naive(7))
    print(naive(8))
    print(naive(9))
    print(naive(10))


def solve(n):
    ans = list(range(1, n + 1))
    for i in range(1, n - 1, 4):
        ans[i], ans[i + 1] = ans[i + 1], ans[i]
    return ans


# check()

t = int(input())
for _ in range(t):
    n = int(input())
    ans = solve(n)
    print(*ans)

あるbitだけについて見たとき、$1～N$ でその bit が立った数が $k$ 個あったら、

• そのbitが立っている数を、できる限り2個ずつ隣接させて並べる
• 奇数だったら、余った1つは最後に持ってくる

とすると、そのbitに関しての総和は最小化できる。
その時、$\left \lceil \frac{k}{2} \right \rceil$ 回、そのbitは和に計上される。

あるbitだけ取り出したP   1 1 0 0 0 1 1 0 1 1 1 1 0 1
累積xor                  1 0 0 0 0 1 0 0 1 0 1 0 0 1
                           ^         ^     ^   ^      1が立ったらすぐさま打ち消すのが良い

全てのbitについてこのように配置できれば全体としても下限になるのだが、 実際には他のbitとの兼ね合いで、必ずしも“1”を2個隣接させられなかったり、奇数の時に最後を“1”にできない可能性がある。

さて、上記の「$4k+2,4k+3$ をswap」解法がどうなっているかというと、

:        |→下2bit
... 1 0 1 0 0
... 1 0 1 0 1
... 1 0 1 1 1
... 1 0 1 1 0
... 1 1 0 0 0
... 1 1 0 0 1
... 1 1 0 1 1
... 1 1 0 1 0
:

4個1セットで考えると、

• 下2bit以外は4つずつ同じ要素が隣接しているので、すぐ打ち消される
• 下2bitも、うまく2個ずつ“1”が隣接する構造になっている

ので、セットが揃っていた場合、全てのbitで下限を達成できる構造になっているのが分かる。

後は、最後の $N$ 付近で、セットの途中で打ち切られるときにどうなるかだが、、、

下2bit以外は、全て“0”か全て“1”かのどちらかであり、途中で切られても下限を達成できる。（立ったらすぐ打ち消し、奇数なら最後に“1”が立つ）

下2bitは

• $N=4k+3$ の時
  • ちょうど4個セットの切れ目となるので、下限を達成できる。
• $N=4k$ の時、“00” で終わる。
  • 下限を達成できる。
• $N=4k+1$ の時、“00”,“01” で終わる。
  • 下1bit目は奇数個だが、最後に“1”が立つのでOK。下限を達成できる。
• $N=4k+2$ の時、“00”,“01”,“10” で終わる。
  • この場合だけ、下1bit目、2bit目がともに奇数個となるが、両方の“1”を同時に最後に持ってくることができないため、下限を達成できない。
  • 最も影響の少ない1bit目の“1”を最後から2番目にすることで、下限+1 は達成できている。

$N=4k+2$ の時以外は下限を達成できる。
$N=4k+2$ の時、他の並べ方でも下限を達成できる方法が無いことを示す。

$1～N-1$ までで各bit毎に“1”が立っている個数を考えると、下1bitのみ奇数、他は全て偶数である。 つまり、$1～N$ まででは「$N$ で立っているbit + 下1bit」が奇数個になる。 下限を達成するためにはこれらを最後、同時に“1”にしなければいけないが、その整数は確実に $N+1$ 以上なので、使うことはできない。
よって、下限を達成する方法はない。

多くは下限を達成でき、達成不可能なとき下限+1ができるので、$4k+2,4k+3$ 番目のswapが最適であることが分かる。

B - Not High Element

• 整数 $N,K$ と長さ $K$ の整数列 $A=(A_1,A_2,\ldots,A_K)$ が与えられます。
  • $A$ の各要素は $1$ 以上 $N$ 以下で相異なることが保証されます。
• $(1,2,\ldots,N)$ の順列 $P=(P_1,P_2,\ldots,P_N)$ に対して $f(P)$ を以下のように定義します。
  • $P$ に対して以下の操作を行うことのできる回数の最大値。
    • $P_i \lt \max(P_1,P_2,\ldots,P_{i-1})$ を満たす $2\le i\le N$ を選び、$P_i$ を先頭に移動させる。
    • つまり、$P$ を $(P_i,P_1,P_2,\ldots,P_{i-1},P_{i+1},\ldots,P_N)$ で置き換える。
• $A$ をprefixに持つような $P$ は $(N-K)!$ 通りありますが、それら全てに対する $f(P)$ の総和を $998244353$ で割ったあまりを求めてください。

• $T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

• $1\le T\le 10^5$
• $1\le K\le N$
• 全てのテストケースにおける $N$ の総和は $5\times 10^5$ 以下
• $1\le A_i\le N$
• $A$ の各要素は相異なる
• 入力される値は全て整数

実験により、以下の仮定に気付く。

• 操作回数を最大化するには、その時点で操作できる最も小さな $P_i$ に操作するのが最適である。
• はじめて要素 $x$ を先頭に持ってきてから、$1～x$ が昇順に並ぶまで（＝$x$ 以下のどの要素にも操作できなくなるまで）、$2^{x-1}$ 回の操作が可能となる。

3 1 5 4 2
1 3 5 4 2    コ はじめて1を先頭に持ってきてから 1～1 が昇順に並ぶまで1回
2 1 3 5 4    ┐ はじめて2を先頭に持ってきてから 1～2 が昇順に並ぶまで2回
1 2 3 5 4    ┘   この時点で3には操作できないので飛ばして、、、
4 1 2 3 5    ┐ はじめて4を先頭に持ってきてから 1～4 が昇順に並ぶまで8回
1 4 2 3 5    │
2 1 4 3 5    │
1 2 4 3 5    │
3 1 2 4 5    │
1 3 2 4 5    │
2 1 3 4 5    │
1 2 3 4 5    ┘

略証

3 1 5 4 2  →  S = {1,2,4}

S={2,5,7}

最も小さい要素に操作          それ以外の操作例
{2,5,7}                       {2,5,7}
{1,5,7}                        │
{5,7}                          │2を飛ばして5に対して操作
 ↓はじめて5に操作             ↓
{1,2,3,4,7}       ←一致→    {1,2,3,4,7}
{2,3,4,7}                     {2,3,4,7}
...                           ...

                      4321
S={1,2,4}  →  f(S) = 1011（2進数）

S              f(S)
{1,2,4}  →    1011
{2,4}    →    1010
{1,4}    →    1001
{4}      →    1000
{1,2,3}  →    0111
{2,3}    →    0110
...

初期状態で自身より大きい値が左側にあるような $P_i$ に対し、$2^{P_i-1}$ の合計が答えとなる。

さて、元の問題に戻って、prefix $A$ のみが固定されている場合を考える。

期待値で考える。操作する要素 $x=1～N$ に対して、$2^{x-1}$ が答えに寄与するかどうかは独立に考えられる。$A$ の最大値を $m$ とする。

• $x$ が $A$ に含まれ、かつ自身より大きい値が左側にある: 確定で $2^{x-1}$
• $x$ が $A$ に含まれ、かつ自身より大きい値が左側にない: 確定で $0$
• $A$ に含まれず、$m$ より小さい: 確定で $2^{x-1}$
• $A$ に含まれず、$m$ より大きい: ※後述

4つめ（※）が、prefix以外の並び順によって寄与が変化するところである。
「$A$ に含まれず、$m$ より大きい」値が全部で $k$ 個あるとすると、この部分の期待値は以下の和となる。

• $x=N-k+1$
  • $k$ 個のうち、$x$ が最初に出現する場合のみダメ。→期待値 $2^{N-k} \times \frac{k-1}{k}$
• $x=N-k+2$
  • $k-1$ 個のうち、$x$ が最初に出現する場合のみダメ。→期待値 $2^{N-k+1} \times \frac{k-2}{k-1}$
• ：
• $x=N-1$
  • $2$ 個のうち、$x$ が最初に出現する場合のみダメ。→期待値 $2^{N-2} \times \frac{1}{2}$
• $x=N$
  • $1$ 個のうち、$x$ が最初に出現する場合のみダメ。（必ずダメ）

期待値に場合の数 $(N-K)!$ をかけたものが答えとなる。

Python3

def solve(n, k, aaa):
    MOD = 998244353
    aaa = [a - 1 for a in aaa]
    tmp_max = -1
    exp = 0
    used = [False] * n
    for a in aaa:
        if tmp_max > a:
            exp += pow(2, a, MOD)
            exp %= MOD
        else:
            tmp_max = a
        used[a] = True
    for a in range(n):
        if used[a]:
            continue
        if a < tmp_max:
            exp += pow(2, a, MOD)
        else:
            exp += pow(2, a, MOD) * (1 - pow(n - a, -1, MOD))
        exp %= MOD
    ans = exp
    for i in range(2, n - k + 1):
        ans *= i
        ans %= MOD
    return ans


t = int(input())
for _ in range(t):
    n, k = list(map(int, input().split()))
    aaa = list(map(int, input().split()))
    ans = solve(n, k, aaa)
    print(ans)

C - Greedy Customers 2

• AtCoder 商店には $N$ 個の品物があります。$i$ 番目の品物は $A_i$ 円です。
• AtCoder 商店に $N$ 人の人が順番にやってきます。各人の所持金は $C$ 円で、以下の手続きを行います。
  • 買い物に使う予算として、$1$ 以上 $C$ 以下の整数 $x$ を一様ランダムに選ぶ。
  • AtCoder 商店に残っている品物の中に $x$ 円以下のものが存在すれば、その中で最も高価なものを $1$ つ購入する。存在しない場合は何も購入せず店を去る。
• AtCoder 商店の経営者であるあなたは、品物が何個売れるか知りたくなりました。$k=0,1,2,\ldots,N$ について、最終的に品物がちょうど $k$ 個売れる確率を $\ \text{mod}\ 998244353$ で求めてください。

• $T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

• $1\le T$
• $1\le N$
• 全てのテストケースにおける $N$ の総和は $100$ 以下
• $1\le A_i \le C \lt 998244353$
• 入力される値は全て整数

$N$ 人の客が選んだ予算の多重集合が等しければ、順番に依らず、品物の売れ方は変わらない。

更に言うと、商品の値段のユニークな種類数を $M$ 個として、実質的に品物の売れ方に差異が生じる予算は $M+1$ 種類の区間に分けられる。 「各客の予算が属する区間」の多重集合が等しければ、品物の売れ方は変わらないと言える。

N=6  A=[2,2,5,9,9,9]  C=15  →  M=3

予算 1    2    5    9   15
区間 [   )[   )[   )[    ]   予算が異なっても、入る区間が一緒なら、品物の売れ方は一緒。
      ↑   ↑   ↑    ↑     4個の区間のそれぞれに計6人の客の予算を配置

つまり、問題はこう言い換えられる。

• $0～M$ の番号が付いた $M+1$ 個の箱に、$1～N$ の番号が付いた $N$ 個のボールを入れる。
• 箱 $i$ に入ったボール $j$ が処理される順番になったら、客 $j$ は、$A$ の（ユニークな）$i$ 番目に小さい値以下の品物が残っていたら購入できる。
  • 箱 $0$ に入っていたら何も購入できない

ここで、問題文の通りの処理では「ボール $1,2,...,N$ の順に処理」することになるが、 「全体でいくつの品物が購入されるか」という点では「箱 $0,1,...,M$ の順に、中に入ったボールを処理」しても変わらない。
つまり、ボールの番号は一旦忘れて、各箱に入った個数のみを添字としたDPができ、番号の付け方は後から考えればよい。

以上を念頭に置きつつ、ひとまず、各箱へボールをいくつ入れるかを固定した時、何個の商品が売れるかを考える。
$Y_i$ を「箱 $i$ に入れたボールの個数」とし、ボールの入れ方の一例を $Y=(Y_0,...,Y_M)$ で表す。

左の箱から累積和を取ったとき、 「商品の個数の累積和 < 実際に商品を購入できたボールの累積和」となることはできない。
つまり以下の表で、$X_i \lt Z_i$ となる $i$ があってはいけない。

          予算    1    2    5    9   15
          区間    [   )[   )[   )[    ]
         index     0    1    2    3

        商品数     0    2    1    3
商品数の累積和 X   0    2    3    6

    ボールの数 Y   1    1    3    1
購入数の累積和 Z   0    1    3    4

例えば $i=2$ の箱に $3$ 個のボールが入れられているとする（$Y_2=3$）。
また $i$ 未満の箱の処理で購入された商品の数は $Z_{i-1}$ で表され、$Z_1=1$ だとわかっている。

         index     0    1    2    3
商品数の累積和 X   0    2   [3]   6    Z2 = min(X2, Z1+Y2)
          客数 Y   1    1   [3]   1       = min( 3, 1 + 3)
購入数の累積和 Z   0   [1]   ?            = 3

この時、$Z_i = \min(X_i,Z_{i-1}+Y_i)$ が成り立つ。上記の“?”には $3$ が入ることとなる。
$Z_0=0$ であり、$i=1,...,M$ の順に計算していくことで、$Y$ を固定した時の全体の購入数が求められた。

これを元に、元の問題を解くためのDPを定義する。

• $\mathrm{DP}[i,j,k]:=i$ 個目の箱までのボールの入れ方および相対的な番号の付け方を決めて、$j$ 個のボールを入れ $k$ 個の商品が売れている確率

$\mathrm{DP}[i-1,j,k]$ からは、新たに箱 $i$ に入れるボールの数を $l=0,...,N-j$ で決めて、

• $\mathrm{DP}[i,j+l,\min(k+l,X_i)]+=\mathrm{DP}[i-1,j,k] \times \left ( \frac{w}{C} \right )^l \times {}_{j+l}C_{l}$

のようにして更新できる。

ただし $w$ は箱が表す区間長を示す。例えば上例の箱 $i=2$ は元の予算に立ち返ると $[5,9)$ の区間を表すので $w=4$ となる。
$ \left ( \frac{w}{C} \right )^l$ は、その箱に $l$ 個のボールが入る確率を表している。

また ${}_{j+l}C_{l}$ は、ボールの番号の付け方も考慮した値とするためにかけている。

最終的に $\mathrm{DP}[M,N,*]$ が答えとなる。

計算量は $O(N^4)$ だが、$j \lt k$ となる $k$ や、$j+l \gt N$ となる $l$ は処理しないという自明な枝刈りをすると、$1/6$ 程度の定数倍がかかるため、間に合う。

Python3

from collections import Counter


def precompute_factorials(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f = f * m % MOD
        factorials.append(f)
    f = pow(f, MOD - 2, MOD)
    finvs = [1] * (n + 1)
    finvs[n] = f
    for m in range(n, 1, -1):
        f = f * m % MOD
        finvs[m - 1] = f
    return factorials, finvs


def solve(n, c, aaa):
    MOD = 998244353
    facts, finvs = precompute_factorials(n, MOD)

    def ncr(n, r):
        return facts[n] * finvs[r] % MOD * finvs[n - r] % MOD

    cnt = Counter(aaa)
    aaa = sorted(cnt.keys())
    m = len(aaa)
    bw = [aaa[0] - 1]
    limit = [0]
    for i in range(m - 1):
        bw.append(aaa[i + 1] - aaa[i])
        limit.append(limit[i] + cnt[aaa[i]])
    bw.append(c - aaa[-1] + 1)
    limit.append(limit[-1] + cnt[aaa[-1]])

    # dp[(i),j,k] = i番目までの隙間にj個置いて有効なのがk個である状態の数
    inv_c = pow(c, -1, MOD)
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for j in range(n + 1):
        dp[j][0] = pow(bw[0] * inv_c, j, MOD)
    for i in range(m):
        ndp = [[0] * (n + 1) for _ in range(n + 1)]
        p = bw[i + 1] * inv_c % MOD
        for j in range(n + 1):
            for k in range(j + 1):
                for l in range(n - j + 1):
                    av = min(k + l, limit[i + 1])
                    ndp[j + l][av] += dp[j][k] * pow(p, l, MOD) * ncr(j + l, l)
                    ndp[j + l][av] %= MOD
        dp = ndp

    return dp[n]


t = int(input())
for _ in range(t):
    n, c = list(map(int, input().split()))
    aaa = list(map(int, input().split()))
    ans = solve(n, c, aaa)
    print(*ans)

D - Greedy Customer

• AtCoder 商店には $N$ 個の品物があり、$i$ 番目の品物は $A_i$ 円です。
• 正整数 $k$ に対し、$f(k)$ を以下の問題の答えとして定義します。
  • 高橋君はお金を $k$ 円持った状態から、$i=1,2,\ldots,N$ の順に以下の行動を行います。
    • 今持っているお金が $A_i$ 円以上ならば $i$ 番目の品物を購入する。
  • 高橋君が買った品物の値段の合計を求めてください。
• $k=1,2,...,M$ に対し、$f(k)$ を求めてください。

• $T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

• $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$
• 入力される値は全て整数

C問題と同じ配点。やることが分かれば実装の複雑さはC問題ほどではないが、考察の難度はこちらの方が高いか。

出力で、個別の $k$ に対して答えるのではなく変な集約処理を施すことを求められているが、 「集約値だからこそ（個別の $k$ の答えを求めずとも）求める方法がある」というよりは、 単に $M$ が大きく、実行時間にI/Oが影響しないようにするためだろう。

（と推測はできるのだが、僅かながらに「実は集約値だからこそなのか？」という迷いは生じるよね）

実際には TLE,MLE となるが、あくまで考察として以下のDPを考える。

• $\mathrm{DP}[i]:=i$ 番目以降の品物を順に購入していくことを考える。
  • 初期所持金を $c=1,2,...$ と増やしていった時、購入できる合計金額が変化する $c$ の集合

これは、$\mathrm{DP}[N+1]=[0]$ とした上で、以下の更新を $i=N,N-1,...,1$ の降順に行うことで求められる。

• $\mathrm{DP}[i]=[\mathrm{DP}[i+1]$ の各要素のうち $A_i$ 未満のもの$] \& [\mathrm{DP}[i+1]$ の各要素に $A_i$ を加算したもの$]$
  • ただし、$\&$ は数列の結合を表す

$c=1,...,A_i-1$ の間は $A_i$ を買えないので $\mathrm{DP}[i+1]$ と等しくなる。 それ以降は $A_i$ を必ず買うので購入金額が $A_i$ だけ増え、後の挙動は $\mathrm{DP}[i+1]$ と等しくなる。

だが、これをそのまま実装すると、$A$ によっては $|\mathrm{DP}[N-i]| \simeq 2^i$ となるので、要素数が多すぎる。 $M$ を超えた要素をその都度取り除いても、$O(NM)$ かかる。

実は各 $\mathrm{DP}[i]$ が保持する値の範囲はもっと少なくていい。

M = 10   A = 3 5 2

     Ai  必要な初期所持金の区間
      -  ⓪①②③④⑤⑥⑦⑧⑨⑩    DPで最終的に必要なのは 0～M の範囲

i=1   3  ⓪①②⓿❶❷❸❹❺❻❼    ●は、○の数列にAiだけ加算したもの
               ~~~~~~~~~~~~~~~~    i=2 にて長い方の●の範囲が求まっていれば、○は復元できる

i=2   5        ⓪①②③④⓿❶❷    i=3 にて長い方の○の範囲が求まっていれば、●は復元できる
               ~~~~~~~~~~          

i=3   2        ⓪①⓿❶❷          i=4 にて長い方の●の範囲が求まっていれば、○は復元できる
                   ~~~~~~

例えば $i=2$ の更新に必要なのは⓪～④の範囲なので、 $\mathrm{DP}[3]$ は上限を $4$ とした範囲が求まっていれば十分ということが分かる。

また、各 $\mathrm{DP}[i]$ は、$\mathrm{DP}[i+1]$ の前か後ろに （$A_i$ の加算の有無はあるが）同じ数列のprefixの一部を付け足した構造となっている。

つまり、まずは $i$ の昇順に、以下を求めておく。

• $L_i:=$ 各 $\mathrm{DP}[i]$ に求められる値の範囲上限
  • 上例では $L_1=10,L_2=7,L_3=4$
• $Y_i:=\mathrm{DP}[i+1]$ から $\mathrm{DP}[i]$ を求める際、左右のどちらに prefix を付け足せば良いか
  • 上例では $Y_1=$左、$Y_2=$右、$Y_3=$左

DPの状態を deque $D$ で管理し、また $D$ 全体に加算する値を offset $s$ で持っておく。

$D=[0],s=0$ で初期化し、$i=N,N-1,...,1$ の順に、

• $Y_i=$右 なら
  • $D$ の先頭要素から順に（$d$ とする）、$d+A_i$ を末尾に追加していく。
  • $d+A_i+s$ が $L_i$ を超えたら終了する。
• $Y_i=$左 なら
  • $D$ の先頭要素から順に（$d$ とする）、$d-A_i$ を計算していく。（後で $D$ の先頭に逆順で追加）
  • $d+s$ が $A_i$ 以上になったら終了する。
  • $s$ に $A_i$ を加算する。

としていけば、$D$ の左右への要素追加を、$A_i$ を考慮しながら実現できる。
$D$ への追加が発生するのは、各初期所持金 $c$ につき高々 $1$ 回なので、全体 $O(N+M)$ で求められる。

$M$ がかなり大きいので、下手なことをすると MLE になる。

Pythonでは、list.append をした時に、 確保したメモリ領域が少なくなってくると、自動的に「今の長さ × 1.125」くらいの領域を確保する。

また、Codon の deque においては、更に大きく $2$ 倍の領域を確保するようになっているっぽい？

• https://raw.githubusercontent.com/exaloop/codon/develop/stdlib/collections.codon
  • _double_cap() が上限を伸ばす関数と思われ、長さを2倍にしている

この挙動は外からいじることはできない。

今回、deque の要素数上限は $M+1$ と分かっているので、 その分だけ領域確保したリングバッファで代替することで、少しメモリを抑えられる。

この時、さらなる省メモリ効果として、 標準の deque ではイテレート中に append 操作をするとエラーになるので、 $d \pm A_i$ した値は一時配列に溜めておく必要があり、deque と一時配列でともに $O(M)$ 領域を必要としていた。 一方、自前のリングバッファの場合はイテレート中の append を実装次第で可能にできるので、一時配列が不要になる。これが何気に大きかった。

Python3

class RingBuffer:
    cap: int
    arr: list[int]
    head: int
    size: int

    def __init__(self, capacity: int):
        self.cap = capacity
        self.arr = [0] * capacity
        self.head = 0
        self.size = 0

    def append(self, x: int):
        tail = self.head + self.size
        if tail >= self.cap:
            tail -= self.cap
        self.arr[tail] = x
        self.size += 1

    def appendleft(self, x: int):
        h = self.head - 1
        if h < 0:
            h += self.cap
        self.head = h
        self.arr[h] = x
        self.size += 1

    def pop(self) -> int:
        self.size -= 1
        tail = self.head + self.size
        if tail >= self.cap:
            tail -= self.cap
        return self.arr[tail]

    def __iter__(self):
        for i in range(self.size):
            idx = self.head + i
            if idx >= self.cap:
                idx -= self.cap
            yield self.arr[idx]

    def __len__(self):
        return self.size


def solve(n, m, aaa):
    limits = [0] * (n + 1)
    limits[0] = m
    for i in range(n):
        a = aaa[i]
        l1 = min(limits[i], a - 1)
        l2 = limits[i] - a
        limits[i + 1] = max(l1, l2)

    dq = RingBuffer(m + 1)
    dq.append(0)
    offset = 0
    for i in range(n - 1, -1, -1):
        a = aaa[i]
        lim = limits[i]
        if a - 1 >= lim - a:
            for b in dq:
                if b + a + offset > lim:
                    break
                dq.append(b + a)
        else:
            counter = 0
            for b in dq:
                if b + offset >= a:
                    break
                counter += 1
                dq.append(b - a)
            for _ in range(counter):
                dq.appendleft(dq.pop())
            offset += a


    ans = 0
    prev = 0
    for c in dq:
        c += offset
        for i in range(prev, c):
            ans ^= i * prev
        prev = c
    c = m + 1
    for i in range(prev, c):
        ans ^= i * prev

    return ans


t = int(input())
for _ in range(t):
    n, m = list(map(int, input().split()))
    aaa = list(map(int, input().split()))
    ans = solve(n, m, aaa)
    print(ans)