No.183

排他的論理和の性質から, $A_i$ を選ぶ順序は順不同である.

$i$ 番目のスイッチまで調べたときに $x$ が作れるかどうかを $B(i, x)$ とすると,

$$B(i + 1, x) = {\rm true} \\ B(i + 1, x \oplus a_i) = {\rm true}$$

という感じで DP で更新していき, 最後に $B(N, *)$ が true となっていく個数を数える.

なお, $x$ は $0 \leq x \leq 32767(2^{15} - 1)$ の値を取りうる.