問題概要
問題ページ
-
-
D - XOR World
問題ページへ移動する
問題文
\(f(A, B)\) を \(A, A+1, ..., B\) の排他的論理和としたとき、\(f(A, B)\) を求めてください。
排他的論理和とは
整数 \(c_1, c_2, ..., c_n\) のビットごとの排他的論理和 \(y\) は、以下のように定義されます。
- \(y\) を二進表記した際の \(2^k\) (\(k \geq 0\)) の位の数は、\(c_1, c_2, ..., c_n\) のうち、二進表記した際の \(2^k\) の位の数が \(1\) となるものが奇数個ならば \(1\)、偶数個ならば \(0\) である。
例えば、\(3\) と \(5\) の排他的論理和は \(6\) です(二進数表記すると: 011 と 101 の排他的論理和は 110 です)。
制約
- 入力は全て整数である。
- \(0 \leq A \leq B \leq 10^{12}\)
問題の考察
排他的論理和の問題。
制約が\(0 \leq A \leq B \leq 10^{12}\)なのでfor文で計算すると明らかに間に合わない。
排他的論理和の問題は、その性質を上手く利用して計算する問題が多く出題されている。
今回の場合には次のような性質を利用する必要がある。
排他的論理和の性質
- 偶数から始まる隣合う2数の排他的論理和は\(1\)
実際に数値を当てはめてみると次のようになります。
隣り合う排他的論理和
- \(10(2) \oplus 11(3) = 1\)
- \(100(4) \oplus 101(5) = 1\)
- \(110(6) \oplus 111(7) = 1\)
- \(1000(8) \oplus 1001(9) = 1\)
- \(1010(10) \oplus 1010(11) = 1\)
\(()\)内は\(10\)進数表記、\(\oplus \)は排他的論理和だが、計算してみると「隣り合う\(2\)数の排他的論理和は\(1\)」であることが分かる。
Bit表記した時に、偶数の最下位桁は\(1\)になり（最下位桁以外は\(2\)の倍数から明らか）、偶数の最下位桁は\(1\)になる。
つまり偶数から始まる隣り合う\(2\)数の差は\(1\)かつ最下位桁以外は一致しているという性質がある。
実際には、開始と終了の文字の偶奇はバラバラであり、次の\(4\)パターンが考えられる。
赤枠で囲まれた部分の排他的論理和は先ほどの説明通り\(1\)であるので、この赤枠が奇数個なら排他的論理和は\(1\)、偶数個なら\(0\)になる。
問題文の通り\(a\)から始まり\(b\)で終わるとすると次のようにまとめられる。
偶奇パターンまとめ
- 偶数から始まり偶数で終わる
- 赤枠が偶数個なら\(0 \oplus b\)
- 赤枠が奇数個なら\(1 \oplus b\)
- 偶数から始まり奇数で終わる
- 赤枠が偶数個なら\(0\)
- 赤枠が奇数個なら\(1\)
- 奇数から始まり偶数で終わる
- 赤枠が偶数個なら\(0 \oplus a \oplus b\)
- 赤枠が奇数個なら\(1 \oplus a \oplus b\)
- 奇数から始まり奇数で終わる
- 赤枠が偶数個なら\(0 \oplus a\)
- 赤枠が奇数個なら\(1 \oplus a\)
これをif文などを使ってコーディングしていくことになる。
コーディングの難易度は高くないが、条件分岐を間違えないように気を付ければ問題ない。
なお、pythonで排他的論理和は^演算子を使う。
ACコード
import sys
def solve():
input = sys.stdin.readline
mod = 10 ** 9 + 7
a, b = list(map(int, input().rstrip('\n').split()))
cnt = b - a + 1
if a % 2 == 0 and b % 2 == 0:
print(b ^ (cnt - 1) // 2 % 2)
elif a % 2 != 0 and b % 2 != 0:
print(a ^ (cnt - 1) // 2 % 2)
elif a % 2 != 0 and b % 2 == 0:
print(a ^ b ^ (cnt - 2) // 2 % 2)
else:
print(cnt // 2 % 2)
if __name__ == '__main__':
solve()