ARC146 C - Even XOR (600)
解説の解法
条件を満たすSがあったとき要素が奇数個の部分集合のXORと同じ値は追加できない
追加すると要素が偶数個でXORが0、になる
逆にそれ以外は追加しても条件を満たした集合のまま
個数の小さい方から動的計画法で個数を求める
$ dp_1 = 2^N
$ 2^N個の内どれを選んでも条件を満たすため
$ i \ge 2で$ dp_i = \frac{dp_{i-1} (2^N - 2^{i-2})}{i}
$ iで割るのは今入れたことにする値を実際に入れる位置が$ i箇所あるため
$ i \ge n+2では大きさが奇数の部分集合で取る値の種類が$ 2^N以上になるので条件を満たす集合は無くなる