[1] Rephrasing the problem

Below, consider coefficients of polynomials modulo \(2\).

From \(x \oplus x=0\), our objective is to find the total \(\mathrm{XOR}\) of \(S\) such that \([x^S](x^{A_1}+x^{A_2}+\dots +x^{A_N})^K\) is \(1\).

Here, we have:

\((x_1+x_2+\dots x_n)^2 \equiv x_1^2+x_2^2+\dots x_n^2 + 2 \sum_{i < j} x_i x_j \equiv x_1^2+x_2^2+\dots x_n^2\).

By using this repeatedly, we can show that:

\((x_1+x_2+\dots x_n)^{2^k} \equiv x_1^{2^k}+x_2^{2^k}+\dots x_n^{2^k}\) .

Thus, if we write \(K\) in binary and have \(K=\sum_{i=1}^{M} 2^{k_i}\ (k_i < k_{i+1})\), it holds that:

\([x^S](x^{A_1}+x^{A_2}+\dots +x^{A_N})^K \equiv [x^S]\prod_{i=1}^{M}(x^{A_1 \times 2^{k_i}} + x^{A_2 \times 2^{k_i}} + \dots + x^{A_N \times 2^{k_i}} )\).

Therefore, the problem can be rephrased into finding the total \(\mathrm{XOR}\) of \(\sum_{i=1}^{M} A_{X_i} \times 2^{k_i}\).

(For this part [1], you can also use Lucas’s theorem.)

[2] Dynamic programming

For the above problem, let us decide \(X_1,\ X_2,\dots,X_M\) in this order to compute the result from the lowest bit. Deciding \(X_m\) after deciding \(X_1,X_2,\dots,X_{m-1}\) will settle the \(k_m\)-th through \((k_{m+1}-1)\)-th bits of \(\sum_{i=1}^{M}A_{X_i} \times 2^{k_i}\). Thus, for \(\sum_{i=1}^{m} A_{X_i} \times 2^{k_i}\), in the later computations (including the computation of the final answer), we just have to consider the \(k_{m}\)-th and higher bits (that is, just \(\lfloor \frac{1}{2^{k_{m}}} \sum_{i=1}^{m} A_{X_i} \times 2^{k_i} \rfloor \)). This value is at most \(2 \max(A)\), so we have to compute:

\(dp[m][s]\): the number, modulo \(2\), of combinations of \(X_1,X_2,\dots X_m\) such that \(\lfloor \frac{1}{2^{k_{m}}} \sum_{i=1}^{m} A_{X_i} \times 2^{k_i} \rfloor = s\)

just for \(s \leq 2 \max(A)\), which can be done in \(O(NM\max(A))\) time.

The \(k_{m}\)-th through \((k_{m+1}-1)\)-th bits of the final answer can be computed from \(dp[m][s]\), but note that \(X_{m+1},X_{m+2},\dots,X_M\) are undecided, so the contribution depends on the parity of \(N^{M-m}\).