解説の解法 条件を満たすSがあったとき要素が奇数個の部分集合のXORと同じ値は追加できない 追加すると要素が偶数個でXORが0、になる 逆にそれ以外は追加しても条件を満たした集合のまま 個数の小さい方から動的計画法で個数を求める $ dp_1 = 2^N $ 2^N個の内どれを選んでも条件を満たすため $ i \ge 2で$ dp_i = \frac{d…