[1]条件の言い換え

条件は、\(S\) の空でない部分集合に「大きさが偶数かつ全要素の \(\mathrm{XOR}\) が \(0\)」であるものが存在しないことと同値です。

[2]要素の追加

全ての条件を満たす集合 \(S\) に対して、\(S\) に追加しても条件を満たすような非負整数の条件を考えます。

\(S\) の部分集合のうち、大きさが奇数であるものを \(1\) 個取り出し、これを \(T\) とします。\(T\) の全要素の \(\mathrm{XOR}\) を \(X\) とします。

もし \(S\) に \(X\) を追加した場合、\(T\) に \(X\) を追加した集合が大きさが偶数であり、かつ全要素の \(\mathrm{XOR}\) が \(0\) となってしまうため条件を満たしません。

逆に、\(S\) の部分集合のうち、大きさが奇数であるものの全要素の \(\mathrm{XOR}\) に必ず一致しない非負整数 \(Y\) は \(S\) に追加した場合 \(S\) は条件を満たすままです。

また、\(S\) の部分集合のうち、大きさが奇数であるものを \(2\) 個取り出し、これを \(T,U\) とします。\(T\) と \(U\) が異なるならば、\(T\) の全要素の \(\mathrm{XOR}\) と \(U\) の全要素の \(\mathrm{XOR}\) も異なることが証明できます。

もし等しいならば、\(T\) と \(U\) のどちらかのみに含まれる要素からなる集合 \(V\) が大きさが偶数かつ全要素の \(\mathrm{XOR}\) が \(0\) になりますが、\(S\) が条件を満たすことと矛盾します。

よって、全ての条件を満たす集合 \(S\) に対して、\(S\) に追加しても条件を満たすような非負整数の個数は「\(2^N - (S\) の部分集合のうち、大きさが奇数であるものの個数\()\)」と等しいです。

[3]動的計画法の利用

\(\mathrm{dp}[i]:=\)「大きさが \(i\) かつ全ての条件を満たす集合の個数」とした動的計画法を考えます。

\(\mathrm{dp}[0]=1\) です。また、上記の議論より遷移は以下のように行うことができます。

\(\begin{cases} \mathrm{dp}[i]=\mathrm{dp}[i-1] \times 2^N\ (i=1)\\ \mathrm{dp}[i]=\frac{\mathrm{dp}[i-1] \times (2^N - 2^{i-2})}{i}\ (i \ge 2) \end{cases}\)

\(i\) で割るのは、要素を追加する順番を考慮する必要があるためです。

上記の式より大きさが \(N+2\) 以上かつ全ての条件を満たす集合は存在しないことがわかります。

よって、この問題を \(\mathrm{O}(N)\) で解くことができます。