AtCoder square869120Contest #3 : C - XORパズル / Solving XOR-Puzzles

問題文

beta 版だと表示が崩れている。

数列 a の中から任意の個数を取り出して、それらの XOR が K になる数列の個数を求めよ、という問題。bit 系の問題は発狂。

解法

「dp(i, j, k) := 数列 a の i - 1 個目までで j 個 XOR し、XOR が k の時の通り数」で DP をやった。j で場合分けし、順列化する（j! を DP の値に掛ける）。最初、j 個に満たないうちに XOR が K になったら即 DP を打ち切りにしていたが、当然その後の組み合わせによっては XOR が K のまま変わらないケースがあるのでミスっていた。