🔖

Atcoder ABC 121 D - XOR World 個人的メモ

2 min read

https://atcoder.jp/contests/abc121/tasks/abc121_d

XOR(\veebar, \oplus)について

  • 0\veebar a=a
  • a\veebar a=0

以上より,

\begin{aligned} a\veebar x&=b\\ x&=b\veebar a \end{aligned}

また,交換法則が成り立つ

a\veebar b=b\veebar b

他にも結合法則,逆元が存在する等の特性があるらしい
アーベル群の定義?らしい

https://ja.wikipedia.org/wiki/XOR交換アルゴリズム#動作原理の証明

今回の話

問題文より

f(A,B)=A\veebar (A+1)\veebar \cdots \veebar B

これを,a\veebar a=0より

f(A,B)=f(0,A-1)\veebar f(0,B)

と変形できる
これは右辺の両関数で0\leqq x\leqq Aの範囲で同じxorを取っているが,xorの特性よりa\veebar a=0だから,重複した区間のxorは全て0になる
で,0\veebar a=aだから,その区間を無視した関数と同じになる

ここから,f(0,n)について考えると

n\veebar (n+1)=1(nは偶数)

という性質が分かるらしい
↓が分かり易い

https://img.atcoder.jp/abc121/editorial.pdf
https://betrue12.hateblo.jp/entry/2019/03/09/224330

さらに考察を進める
例としてf(0,6)を考えてみると,以下の様になる

\begin{aligned} f(0,6)&=0\veebar 1 \veebar 2 \veebar 3 \veebar 4 \veebar 5 \veebar 6\\ &=\{(0\veebar 1) \veebar (2 \veebar 3)\} \veebar (4 \veebar 5) \veebar 6\\ &=\{1\veebar 1\}\veebar 1\veebar 6\\ &=0\veebar1\veebar 6\\ &=7 \end{aligned}

以上の様な例を考えると以下のことが分かるらしい
m\in \mathbb Z(mは整数)とするとf(N)は以下の様に場合分けできる

\begin{aligned} f(0,4m)&=4m\\ f(0,4m+1)&=1\\ f(0,4m+3)&=0\\ f(0,4m+2)&=f(0,4m+1)\veebar (4m+2)\\ &=1\veebar (4m+2)\\ &=(4m+3)\\ \end{aligned}

1\veebar (4m+2)=(4m+3)となるのは,4m+2は偶数なので2進数の1桁目が必ず0,だから1とのxorをとると1桁目が1になる

よって,以上を実装すればおk

def solve(n):
    """F(0,n)"""
    remain = n % 4
    if remain == 0:
        res = n
    elif remain == 1:
        res = 1
    elif remain == 2:
        res = n + 1
    else:
        res = 0
    return res
 
 
A, B = map(int, input().split())
 
if A == 0:
    print(solve(B))
else:
    print(solve(A - 1) ^ solve(B))

もう少し凝って実装すると以下の様な感じ
以下の場合分けに則って実装している

  • nが奇数
    以下の場合分けをbit演算で実装
    • n=1\ mod\ 4(nを4で割った余りが1)ならf(0,n)=1
      つまりnを2進数で表した時の2桁目が0
    • n=3\ mod\ 4(nを4で割った余りが3)ならf(0,n)=0
      つまりnを2進数で表した時の2桁目が1
  • nが偶数
    f(0,n)=n\veebar f(0,n-1)で再帰
def func(n):
    """F(0,n)"""
    if n & 1:
        # 奇数
        n >>= 1
        return ~n & 1
    else:
        # 偶数
        return n ^ func(n - 1)
 
 
A, B = map(int, input().split())
 
if A == 0:
    print(func(B))
else:
    print(func(A - 1) ^ func(B))

参考

https://drken1215.hatenablog.com/entry/2019/03/09/224100
http://www.cc.kyoto-su.ac.jp/~yamada/ap/xor.html
https://yamakasa.net/atcoder-abc-121-d/
https://atcoder.jp/contests/abc121/submissions/5580843
https://qiita.com/7shi/items/41d262ca11ea16d85abc#notとの併用