個人的に一番 straight-forward であるように感じた方針を解説します。

表記の簡便性のため数列 \(a\) の \(L\) 番目から \(R-1\) 番目の要素からなる数列を \(a[L,R)\) のように表します。

まず、前の品物から順に DP をしていくことを考えましょう。

• \(\mathrm{dp}[i][c]\) : 品物 \(i\) まで見て残金が \(c\) 円の時に以降で何円使うか？

という DP を考えます。明らかに次式が成り立ちます：

\[\mathrm{dp}[i][c] = \mathrm{dp}[i+1][c-A[i]]+A[i]\text{ if } c \geq A[i] \text{ else } \mathrm{dp}[i+1][c]\]

この DP を観察してみると、DP の遷移がある種の区間の平行移動となっているという良い性質に気づき、そこから再帰的な遷移を構成できます。具体例を挙げて説明します。例えば \(M=6\) だとします。

(1) \(A[0] = 8\) のとき

\(\mathrm{dp}[0][0,7)\) は \(\mathrm{dp}[1][0,7)\) と一致します。よって \(\mathrm{dp}[1][0,7)\) を計算した上で \(\mathrm{dp}[0][0,7)\) に値をそのまま書き込めばよいです。

(2) \(A[0] = 2\) のとき

• \(\mathrm{dp}[0][0,2)\) は \(\mathrm{dp}[1][0,2)\) と一致、
• \(\mathrm{dp}[0][2,7)\) は \(\mathrm{dp}[1][0,5)\) の各要素に 2 を足したものと一致

します。よって「\(\mathrm{dp}[1][0,5)\) の各要素に \(2\) を足したもの」を計算できれば、その値を \(\mathrm{dp}[0][2,7)\) に書き込んだ上で \(\mathrm{dp}[0][0,2)\) には \(\mathrm{dp}[0][2,4)\) から \(2\) 引いたものを書き込めばよいです。

(3) \(A[0] = 5\) のとき

• \(\mathrm{dp}[0][0,5)\) は \(\mathrm{dp}[1][0,5)\) と一致、
• \(\mathrm{dp}[0][5,7)\) は \(\mathrm{dp}[1][0,2)\) の各要素に \(5\) を足したものと一致

します。よって \(\mathrm{dp}[1][0,5)\) を計算できれば、その値を \(\mathrm{dp}[0][0,5)\) に書き込んだうえで \(\mathrm{dp}[0][5,7)\) には \(\mathrm{dp}[0][0,2)\) から \(5\) 足したものを書き込めばよいです。

(1)(2)(3) をまとめると、「品物を前から見ていき、残金区間を大きく覆う方に注目して、そちらを計算したうえで残りの部分をその情報から復元する」という操作を再帰的に繰り返していくというアルゴリズムを導くことが出来ます。

この種の再帰的な構造は再帰関数を用いるとスッキリかつ良い計算量で実装することが出来ます。(「再帰関数を使う方針を選ぶと簡潔に書ける」という点に気づくことがこの方針の肝要な部分でしょう。UnionFind やマージテクなどの方針を選ぶと計算量が悪化してしまいます。)
計算量は \(\mathrm{O}(N+M)\) で非常に高速です。

• 実装例(Python, codon)

T = int(input())
for t in range(T):
    N, M = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]
    dp = [0] * (M + 1)

    # 開始金額 : [L,R)
    # i 個の品物を見た時点で
    # - ここまでの購入金額が L 円
    # - 今の残金が [0,R-L) 円
    def dfs(i, L, R):
        if i == N:
            for j in range(L, R):
                dp[j] = L
        else:
            a, d = A[i], R - L
            if d < a:
                dfs(i + 1, L, R)
            elif 2 * a <= d:
                dfs(i + 1, L + a, R)
                for j in range(L, L + a):
                    dp[j] = dp[j + a] - a
            else:
                dfs(i + 1, L, L + a)
                for j in range(L + a, R):
                    dp[j] = dp[j - a] + a

    dfs(0, 0, M + 1)
    ans = 0
    for i in range(1, M + 1):
        ans ^= i * dp[i]
    print(ans)