目次
文書の過去の版を表示しています。
AtCoder Beginner Contest 121 D問題メモ
C問題までは考察より実装。B問題はPythonならNumPy使えと言われた気がした。
D - XOR World
問題
- 2つの正整数 $A,B$ が与えられる
- $\oplus$ を、排他的論理和の演算子とする
- $f(A,B)=A \oplus (A+1) \oplus ... \oplus B$ を求めよ
- $0 \le A \le B \le 10^{12}$
解法
まず排他的論理和の性質から、$f(A,B) = f(1,B) \oplus f(1,A-1)$ である。
f(1,A-1): 1 2 3 .. A-2 A-1
XOR f(1, B): 1 2 3 .. A-2 A-1 A A+1 ... B-1 B
----------------------------------------------------
`-- 打ち消し合う --' A A+1 ... B-1 B
なので、1から$N$ までの累積排他的論理和が求められればよい。
実験してみる。すると、1桁目とそれ以外を分離すると、特徴が見えてくる。
N bit f(1,N) 0 0000 0000 1 0001 0001 2 0010 0011 3 0011 0000 4 0100 0100 5 0101 0001 6 0110 0111 7 0111 0000 8 1000 1000 9 1001 0001 10 1010 1011 11 1011 0000 12 1100 1100 13 1101 0001 14 1110 1111 15 1111 0000 ...
1桁目の部分は、2進数が0,1,0,1,…となるので、累積XORは0,1,1,0,…となる。
それ以外の部分は $N$ が奇数の時0となり、偶数の時は $N$ のままとなる。
D問題にしては、わりと実験しやすく法則も気付けば単純なので、正解率は高かった模様。証明は解説pdfがエレガント。
a, b = map(int, input().split()) x = lambda n: (n % 4 in (1, 2)) + (0 if n % 2 else n // 2 * 2) print(x(max(0, a - 1)) ^ x(b))
