# ABC121 D - XOR World

# 概要

  • f(A,B)f(A,B)A,A+1,...,BA, A+1, ..., Bの排他的論理和(XOR)とする
  • f(A,B)f(A,B)を求めよ

# 思考

  • 問題を見てf(0,B)f(0,A1)f(0,B) - f(0,A-1)な気がする
  • 制約を見るとO(logN)O(logN)O(1)O(1)らしい
  • 手元で実験する
  • 桁ごとで見ていくと良さそう
  • 実装する
  • 入力例1の時点で詰まる

ここで30分終了, 時間をあけてもう一度書き直す

  • 書き直しても入力例1が通らない

さらに1時間経過してもわからないので, 解説を見る

  • f(0,B)f(0,A1)f(0,B) - f(0,A-1)ではない
  • f(0,B)f(0,B) xor f(0,A1)f(0,A-1)
    • a xor b = cからc xor b = aが求められる
  • 1桁ごとに1がいくつ出るかを求めれば良い
    • 1が出た数の偶奇で判定できる

# 他の解法(editorial)

隣り合う数字のxorをとると1になることがわかる。これは実験すればわかる。

例えばn=5の時は

1xor2xor3xor4xor51 xor 2 xor 3 xor 4 xor 5
=(0xor1)xor(2xor3)xor(4xor5)= (0 xor 1) xor (2 xor 3) xor (4 xor 5)
=1xor1xor1= 1 xor 1 xor 1
=1= 1

のように求められる。

従って, この性質を用いればO(1)O(1)で解ける。

# 提出

# 気づいたこと

  • 同じ処理が生まれる時は関数化すると綺麗に書ける
    • 今回のように関数で書ける場合はまさにそれ
  • 上限をギリギリにしなくても良い場合は余裕を持ってやると楽
Last Updated: 2019-9-11 23:07:16