F - Unfair Nim AtCoder Beginner Contest 172
解答
(A[0]-x)^(A[1]+x) == A[2]^...^A[N-1]になるようなxがあるかという問題である
a2 =A[0]-x, b2 =A[1]+xとして、a2とb2を求める事にする
問題文より、a2は以下を満たす最大の値になる
0 <= a2 <= A[0]
a2 + b2 = A[0] + A[1]
a2 ^ b2 = A[2]^....A[N-1]
ここで足し算は繰り上がりが面倒なので
式変形してbit毎に独立した問題にすることを考える
a2 & b2 = (a2+b2 - (a2^b2)) / 2
より
S, Xが与えられるので
「以下を満たす最大のa2を求めよ」という問題が解ければこの問題が解ける
0 <= a2 <= A[0]
a2 & b2 = S
a2 ^ b2 = X
これは自然な桁dpで解ける
類題
------------------------------------------------------------------------------------
式変形をせず、問題通りにA[0]からA[1]にbit毎に渡して行く解法もあるらしい
とても奇麗なので書いておこうと思う。
ビットごとに下から考えて、今見ている桁のビットをA[0]からA[1]に配る場合と配らない場合で遷移する
ビットを送るか否かで最下位ビットのxorは変わらないので、それを満たさない場合はINFを返していい
