🔖

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

2021/01/26に公開

競技プログラミング

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

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

今回の話

問題文より

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は偶数)

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

さらに考察を進める
例として $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になる

よって，以上を実装すればおｋ

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://yamakasa.net/atcoder-abc-121-d/

Discussion