読者です 読者をやめる 読者になる 読者になる

SRM 543 Div2 Medium EllysXors

TopCoder Statistics - Problem Statement
要復習

問題

LからRまでの数をXORして得られる値を求めよ

解答

全然分からなかったので解答を見る.
まず重要な性質から.1からXまでのXORをxor(X)とするとLからRまでのXORはxor(L-1) XOR xor(R)で表される.これはxor(L-1) XOR xor(L-1) = 0となってxor(R)の1〜L-1までの値が相殺されることを利用する.
次にxor(X)には周期性が存在し,その値はmod 4の4通りで表される.
SRM 543 DIV 1 easy EllysXors | smokycat.info

うーん難しい,Div1のsubmission rateが89%, success rateが84%なのはさすがだなと思う.