SRM543 Div2 Medium Div1 Easy EllysXors

問題概要

Problem Statement
1≦L≦R≦4*109を満たすL,Rについて、
f(L,R)=L XOR L+1 XOR ... XOR R とするときf(L,R)の値を求めよ。

※XORについて:wikipedia:排他的論理和

方針

ナイーブに実装するとTLEするので、短縮する方法を考える。

解法

※以下A XOR BをA^B、二進数を(XXX)と表す。

f(L,R)=f(1,L-1)^f(1,R)

A^B=B^A,A^B^B=A,A^B=C⇔A=B^Cであることから、
f(L,R)=f(1,L-1)^f(1,R)であることを示す。

f(1,R)=1^2^...^L-1^L^(L+1)^...^b=f(1,L-1)^f(L,R)
よってf(L,R)=f(1,L-1)^f(1,R)

これでf(1,L-1)とf(1,R)が分かれば、f(L,R)は求められることがわかる。

f(1,x)の周期性

f(1,x)を試しに計算してみる。

x=1:1=(1)=1
x=2:1^2=(01)^(10)=(11)=3
x=3:1^2^3=3^3=(11)^(11)=(00)=0
x=4:1^2^3^4=0^4=(000)^(100)=(100)=4
x=5:1^2^3^4^5=4^5=(100)^(101)=(001)=1
x=6:1^2^3^4^5^6=1^6=(001)^(110)=(111)=7
x=7:1^2^3^4^5^6^7=7^7=(111)^(111)=(000)=0
x=8:1^2^3^4^5^6^7^8=0^8=(0000)^(1000)=(1000)=8
...

この計算から以下の法則が導ける。

  • x MOD 4=1 ならば 1
  • x MOD 4=2 ならば x+1
  • x MOD 4=3 ならば 0
  • x MOD 4=0 ならば x

(証明は省略)

ソースコード

以上からソースコードはこうなる。

class EllysXors {
public:
    long long getXor(long long L, long long R) {
        return f(L-1)^f(R);
    }
    long long f(long long x){
        if (x%4==1) return 1;
        else if (x%4==2) return x+1;
        else if (x%4==3) return 0;
        else return x;
    }
};

別解

ナイーブな実装でもlong longをunsigned intに置き換えれば、
間に合うらしいです。(参考の記事を参照)