yukicoder No.2672 Subset Xor Sum (NUPC2023-B)
$ N \leq 5001 の場合における解法の別解を説明します。（DPで解くという点では同じです）
$ \mathrm{dp}[i][j][k][l] := A の$ i 番目までの要素の部分列であって、総XORが$ j であり、$ i 番目までの要素の中で 選ぶ という選択を行ったかどうかのフラグを$ k 、$ i 番目までの要素の中で 選ばない という選択を行ったかどうかのフラグを$ l とした時、これらを満たすものは存在するかどうか(bool)
というDPを考えます。
初期値は $ dp[0][0][0][0] = \mathrm{true} です。
$ \mathrm{dp}[i-1][j][k][l] からの遷移は、
$ i 番目の要素を選ぶ時、
$ \mathrm{dp}[i][j \oplus A[i]][1][l] = \mathrm{dp}[i-1][j][k][l]
$ i 番目の要素を選ばない時、
$ \mathrm{dp}[i][j][k][1] = \mathrm{dp}[i-1][j][k][l]
となります。
最終的に、$ \mathrm{dp}[N][0][1][1] が $ \mathrm{true} ならば Yes、そうでなければ No となります。
（1回でも選ぶという選択をしていれば部分列の長さは$ 1 以上であり、1回でも選ばないという選択をしていれば部分列の長さは$ N-1 以下であることが分かるからです。）
公式解説同様、$ j の範囲は$ [0, 2^{13}) を考慮する必要があることに注意して下さい。