Pの競プロ記

競技プログラミングに関することを書きます。

EllysXors (SRM543 div2 medium)

解法・感想など


自力では解けなかったので他の方々の記事を参考にしました、感謝。

この問題はLからRまでのxorを解くという問題ですが、やることは「1からNまでのxorを求めることができるか」ということになります。

なぜそういえるのか? → 打ち消しあうからです。
だからLからRまでのxorを求めるのですが、実際は(1からL−1までのxor) xor (1からRまでのxor)で求めることができます。

どのようにして1からNまでのxorを求めるか? → MOD 4の性質を用います。
自分で手で書いてみると分かるのですが、規則性があります。

(10) (2) (1からNまでのxor)
========================
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

これをまとめると、

N % 4 == 0 → N
N % 4 == 1 → 1
N % 4 == 2 → N+1
N % 4 == 3  → 0

いやー面白いですね。
これを当てはめるだけで解くことができます。


ちなみにlong longで愚直にLからRまでループを回すともちろんTLEになるのですが、
unsigned intに直してからループ回すとTLEにならずに解くことができます。


ソースコード

class EllysXors {
public:
  long long f(long long n){
    if(n % 4 == 0) return n;
    if(n % 4 == 1) return 1;
    if(n % 4 == 2) return n + 1;
    if(n % 4 == 3) return 0;
  }

  long long another(long long L, long long R){
    unsigned int LL = L;
    unsigned int RR = R;
    unsigned int ans = 0;
    for(unsigned int i = LL; i <= RR; i++) ans ^= i;
    return (long long)ans;
  }

  long long getXor(long long L, long long R) {
    return f(L - 1) ^ f(R);
    //return another(L,R);
  }
};