ABC121 D - XOR World メモ

XORの性質とか知らないのでアでした、あと D 解けてる人多くてビックリ

問題概要

以上 以下の全ての整数の XOR 和を求めよ。

• 制約：

問題リンクは こちら から

解説

ここからは と の XOR を で表すことにします。

言い換え

XOR の性質として、

• 同じ数の XOR は０ ：

があります。

問題上の は、この性質を用いれば

これは 以上 以下の部分で数がダブり、その部分における XOR 和が 0 になるからです。

よって、 から までの XOR 和は、 から までの XOR 和と から までの XOR 和の XOR と等しくなります。

0からXまでのXOR和を求める

以上のことから、 から までの XOR 和と から までの XOR 和さえ求めればよいです。

ここで実験。適当に で を求めると

 x    bin    f(0,x)
-------------------
 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

実験より、が

• のとき：
• のとき：
• のとき：
• のとき：

となります。これで が求められるようになったので、この問題は解けました。

ソースコード

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(void){
    ll a, b; cin >> a >> b; a--;
    ll xa, xb;
    if(a % 4 == 0) xa = a;
    else if(a % 4 == 1) xa = 1;
    else if(a % 4 == 2) xa = a+1;
    else xa = 0;

    if(b % 4 == 0) xb = b;
    else if(b % 4 == 1) xb = 1;
    else if(b % 4 == 2) xb = b+1;
    else xb = 0;

    cout << (ll)(xa^xb) << endl;

    return 0;
}