AND OR XOR

Claim. 음이 아닌 정수 $a$, $b$, $c$에 대해, 다음 두 조건은 동치이다.

$$(a \,\&\, b) = (b \,|\, c) = (c \oplus a) \iff (a = b) \wedge (c = 0).$$

Proof. $(\Rightarrow)$ $a$, $b$, $c$를 이진수로 생각한 뒤, 자릿수별로 나누어 분석하자. 먼저 $a$, $b$, 가 단일 비트를 가진 정수, 즉 또는 이라고 가정하자. 이때 가능한 를 다음과 같이 찾을 수 있다.

• $(a \,\&\, b) = (b \,|\, c) = (c \oplus a) = 0$이라 가정하자. 이때, $(b$이므로 이어야 한다. 또한 이고 이므로 이어야 한다. 따라서, 이어야 한다.

따라서, 위 조건을 만족하는 $(a, b, c)$는 $(0, 0, 0)$이나 $(1, 1, 0)$뿐임을 알 수 있다. 위와 같이 찾지 않고, 가능한 후보가 $$개뿐이므로 전부 시도해 보아도 된다.

$a$, $b$, $c$가 한 개보다 많은 비트를 가질 수 있는 일반적인 경우에 대해서 생각하면, 모든 비트 자리별로 위 조건이 성립해야 한다. 따라서 $c$는 모든 비트가 $0$이어야 하고, $a$와 $b$는 비트끼리 값이 일치해야 된다. 이것은 , 이 모두 성립해야 한다는 뜻이다.

$(\Leftarrow)$ 세 값을 모두 계산해 보면 $a$가 됨을 알 수 있다.

위 성질을 파악했다면, 이후는 $a_i = a_j$, $a_k = 0$인 서로 다른 세 인덱스 의 경우의 수를 구하는 문제와 같다. 수열에서 값이 인 수의 개수를 라 하자. 인 경우와 인 경우로 나누어 센다.

• $a_i = 0$인 경우, 총 $c_0(c_0-1)(c_0-2)$가지 경우가 있다.

수열에 존재하는 모든 값에 대해 위의 값을 더하면 문제를 해결할 수 있다. 각 값의 개수를 세는 것은 정렬이나 std::map을 이용할 경우 $O(n \log n)$에, std::unordered_map을 이용하면 $O(n)$에 가능하다.