けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 121 D - XOR World (400 点)

みんな早い...!!!

問題へのリンク

問題概要

2 つの整数  A, B ( A \le B) が与えられる。 A 以上  B 以下のすべての整数の XOR 和を求めよ。

制約

  •  0 \le A \le B \le 10^{12}

「A 以上 B 以下」と、「XOR の引き算」とは

まず「 A 以上  B 以下の値の総和を求めよ」という問題は、「 X 以下の値の総和を求めよ」という問題だと思うことができる:

  •  B 以下の値についての答えから
  •  A-1 以下の値についての答えを引く

ここで「引く」という行為は、XOR 和においては XOR 和を取ること自体をさす。

一応そのことをちゃんと詰めてみる。引き算は足し算の逆として定義される。つまり  b - a とは  a + x = b を満たす  x のことである。

このことを XOR について考えてみる。すなわち

 a ^  x = b

を満たす  x とはなにかを考えてみる。両辺から  a ^ をとると  a ^  a = 0 より

 x = a ^  b

となる。つまり、XOR の世界では「足し算」も「引き算」も一緒なのだ。この考え方はすごく出て来る。

一応このことを知らなくても、

  •  Q = 0 ^  1 ^  2 ^  \dots ^  (A-1) ^  A ^  (A+1) ^  \dots ^  B
  •  P = 0 ^  1 ^  2 ^  \dots ^  (A-1)

とが求められていたら、

  •  Q ^  P =  A ^  (A+1) ^  \dots ^  B

となってこれが答えになっているので、一般に「 X 以下の整数の XOR 和」が求められればいいことは自然に導ける。

X 以下の整数の XOR 和

ひとまず桁ごとに考えるのが XOR の定石ではあると思う。つまり、 d 桁目のみに着目したときに、 0 から  X までの整数を並べたときに  d 桁目に 1 が立っているものが奇数個か偶数個かを判定する問題ということになる。

今回は、結果的に実験してみるのが早い気がしていて 15 あたりまで書いてみると、

X XOR 和
0 0
1 1
10 11
11 0
100 100
101 1
110 111
111 0
1000 1000
1001 1
1010 1011
1011 0
1100 1100
1101 1
1110 1111
1111 0

という感じになっている。気づくことは

  •  X が奇数のときは  0 1 を繰り返している (全体として  4 個ごとに足すと  0 になっている)

ということ。その証明は後に回すとして、この性質を利用すると

  •  X が奇数のときは、 \frac{X+1}{2} が偶数なら  0、奇数なら  1
  •  X が偶数のときは、 X+1 が奇数なのでその答えから  X+1 を引く (XOR の意味で足す)

とすれば求められる。

#include <iostream>
using namespace std;

long long oddsolve(long long a) { return (a+1)/2 % 2; }
long long solve(long long a) {
    if (a % 2 == 1) return oddsolve(a);
    else return oddsolve(a+1) ^ (a+1);
}
int main() {
    long long A, B; cin >> A >> B;
    cout << (solve(B) ^ solve(A-1)) << endl;
}

X が奇数のときの証明の概略

  • 0 ^ 1 = 1
  • 2 ^ 3 = 1
  • 4 ^ 5 = 1
  • 6 ^ 7 = 1
  • ...

というように、連続する偶数と奇数の XOR 和が 1 になっていることを示せばよい (偶数の方が小さいものとする)。 k を整数として、

  • 偶数  2k は一の位が 0 である (10110 みたいな感じ)
  • 奇数  2k+1 は、 2k の一の位を 1 にしたものである (10110 に対して 10111 にする感じ)

よって、 2k ^  (2k+1) は、一の位のみ 1 で、十の位以上はすべて 0 になる。