水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

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

  • 問題文

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 のまま変わらないケースがあるのでミスっていた。

 

  • 解答

f:id:babcs2035:20180604223231p:plainf:id:babcs2035:20180604223302p:plain

Submission #2618134 - square869120Contest #3