[1] 問題の言い換え

以下、多項式の係数については \(\bmod 2\) で考えます。

\(x \oplus x=0\) より \([x^S](x^{A_1}+x^{A_2}+\dots +x^{A_N})^K\) が \(1\) であるような \(S\) の総 \(\mathrm{XOR}\) を求めればいいです。

ここで、

\((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\)

が成り立ちます。これを繰り返し用いると

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

が成り立つことが示せます。

よって \(K\) の二進法表記を考えて \(K=\sum_{i=1}^{M} 2^{k_i}\ (k_i < k_{i+1})\) が成り立つとき、

\([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}} )\)

が成り立ちます。よって問題は「\(\sum_{i=1}^{M} A_{X_i} \times 2^{k_i}\) の総 \(\mathrm{XOR}\) を求めよ」という問題に言い換えられます。

[2] 動的計画法

[1] で言い換えた問題について、\(X_1,\ X_2,\dots,X_M\) の順に決めて、（二進法で）下の桁から計算していきます。\(X_1,X_2,\dots,X_{m-1}\) を決めた後、\(X_m\) を決めたとき、\(\sum_{i=1}^{M}A_{X_i} \times 2^{k_i}\) の \(k_m\) 桁目から \(k_{m+1}-1\) 桁目が新たに確定します。よって \(\sum_{i=1}^{m} A_{X_i} \times 2^{k_i}\) について、これ以降の計算（および最終的な答えの計算）では \(k_{m}\) 桁目以降だけ（すなわち、\(\lfloor \frac{1}{2^{k_{m}}} \sum_{i=1}^{m} A_{X_i} \times 2^{k_i} \rfloor \) だけ）考えればいいです。この値は \(2 \max(A)\) 以下であるため、

\(dp[m][s]\): \(\lfloor \frac{1}{2^{k_{m}}} \sum_{i=1}^{m} A_{X_i} \times 2^{k_i} \rfloor = s\) となる \(X_1,X_2,\dots X_m\) の組の数 \(\bmod 2\)

は \(s \leq 2 \max(A)\) の範囲だけ計算すればよく、これは \(O(NM\max(A))\) で計算できます。

最終的な答えの \(k_{m}\) 桁目から \(k_{m+1}-1\) 桁目は \(dp[m][s]\) から計算できますが、 \(X_{m+1},X_{m+2},\dots,X_M\) は決めていないため、 \(N^{M-m}\) の偶奇によって寄与が変わることに注意しましょう。