[AtCoder] ABC 121 D – XOR World
問題
https://atcoder.jp/contests/abc121/tasks/abc121_d方針
排他的論理和の性質
\( \mathrm{XOR} \) を \(\oplus\) で表すとします。
まず排他的論理和の性質として次の二つがあります。
- \( 0 \oplus x \ = x \)
-
\( x \oplus x = 0 \)
\( f(A, B) \) の式変形
\( f(A, B) = A \oplus (A + 1) \oplus \cdots \oplus B\)
ここで、\(f(0, B) \) を考えます。
\begin{eqnarray}
f(0, B) &=& 0 \oplus 1 \oplus \cdots \oplus(A – 1) \oplus A \oplus (A + 1) \oplus \cdots \oplus B \\
f(0, B) &=& f(0, A-1) \oplus f(A, B)
\end{eqnarray}
上式に左から \( f(0, A-1) \) の排他的論理和を作用させると、
\begin{eqnarray}
f(0, A-1) \oplus f(0, B) &=& f(0, A-1) \oplus f(A, B)\\
f(0, A-1) \oplus f(0, B) &=& f(0, A-1) \oplus f(0, A-1) \oplus f(A, B)\\
f(0, A-1) \oplus f(0, B) &=& 0 \oplus f(A, B)\\
f(A, B) &=& f(0, A-1) \oplus f(0, B)
\end{eqnarray}
\( f(0, n) \) の値
\begin{eqnarray}
f(0, 0) &=& 0 \\
f(0, 1) &=& 1 \\
f(0, 2) &=& 3 \\
f(0, 3) &=& 0 \\
f(0, 4) &=& 4 \\
f(0, 5) &=& 1 \\
f(0, 6) &=& 7 \\
f(0, 7) &=& 0 \\
f(0, 8) &=& 8 \\
f(0, 9) &=& 1 \\
f(0, 10) &=& 11 \\
\end{eqnarray}
\begin{eqnarray}
f(0, 4m) &=& 4m\\
f(0, 4m + 1) &=& 1\\
f(0, 4m + 3) &=& 0
\end{eqnarray}
となっていることが分かります。\( f(0, 4m + 2) \) は、
\[f(0, 4m + 2) = f(0, 4m + 1) \oplus (4m + 2) = 1 \oplus (4m + 1)\]
として、求めることができます。よって、\(f(A, B)\) を求めることができます。
コード
提出したコード
https://atcoder.jp/contests/abc121/submissions/5830888排他的論理和の計算
ll func(ll n) {
if(n <= 0) return 0;
if(n % 4 == 0) {
return n;
}else if(n % 4 == 1) {
return 1;
}else if(n % 4 == 2) {
return 1 ^ n;
}else {
return 0;
}
}