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$, $c$가 단일 비트를 가진 정수, 즉 $0$ 또는 $1$이라고 가정하자. 이때 가능한 $(a, b, c)$를 다음과 같이 찾을 수 있다.

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

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

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

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

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

• $a_i = 0$인 경우, 총 $c_0(c_0-1)(c_0-2)$가지 경우가 있다.
• $a_i = v \neq 0$인 경우, 총 $c_v (c_v-1) c_0$가지 경우의 수가 있다.

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