18381 XOR과 집합과 트리와 쿼리

https://www.acmicpc.net/problem/18381

어떤 사람들은 $f(S) = f(\{a\})$와 같이 결국 하나의 원소로 생성된다는 것을 직관을 통해 알아내어 풀 것이다. 본문에서 이 추측이 왜 올바른지 설명하고, 문제의 풀이에 대해 간략하게 정리하였다. 쓸데없이 복잡해졌다고 생각하므로 더 좋은 증명에 대한 의견을 얻을 수 있으면 하는 마음이다.

추측이 옳은 이유

$0 \le x < 2^{1001}$을 만족하는 정수 $x$는 벡터 공간 $\mathbb{Z}_2^{1001}$의 원소로 볼 수 있다. 이러한 대응은 $x$를 이진법으로 전개하여, $k$번째 자리를 $k$번째 $\mathbb{Z}_2$에 대응시킴으로써 가능하고, 역으로 대응시키는 것도 가능하다. 앞으로의 풀이에서 맥락에 따라 $\mathbb{Z}_2^{1001}$는 벡터 공간 혹은 0보다 크거나 같고 $2^{1000}$보다 작은 정수들로 이루어진 집합으로 해석된다. $\oplus$는 $\mathbb{Z}_2^{1001}$위의 덧셈, 즉 정수의 xor 연산을 나타낸다. $S$를 0을 포함하지 않는 $\mathbb{Z}_2^{1001}$의 부분집합이라고 하면, 조건 1에 의해 조건을 만족하는 $V_S = f(S) \cup \{0\}$는 $\mathbb{Z}_2^{1001}$의 부분공간이다.

문제의 조건을 모두 만족하는 집합 $f(S)$에 대해, 이는 어떤 $a$에 대해 $f(\{a\})$으로 표현될 수 있다. 0이 아닌 원소 $a \in \mathbb{Z}_2^{1001}$에 대해, $\mathbb{Z}_2^{1001}$의 원소를 정수로써 다루었을 때 $2^{k} a$, $k \in \mathbb{Z}$ 꼴로 표현되는 모든 원소를 $a$의 shift라고 하자. $s(a)$를 $a$의 모든 shift로 이루어진 집합이라고 하자. 모든 $S \subset \mathbb{Z}_2^{1001} \setminus \{0\}$에 대해, $V_S$는 어떤 $a$에 대해 $s(a)$로 생성되는 부분 공간 $\langle s(a) \rangle$과 같음을 보일 것이다.

$f(S)$에 포함된 가장 작은 양의 정수를 $a$라고 하고, $a$를 이진 전개하였을 때의 길이를 $d$라고 하자. $a$가 짝수이면 조건 3에 의해 $a/2$가 $f(S)$에 포함되고 이는 $a$의 최소성에 모순이므로 $a$는 홀수이다. $s(a)$는 선형독립이고, 각 원소는 $2^i a$꼴로 나타남을 관찰하자. $\langle s(a) \rangle$에서 $s(a)$는 기저를 이룬다. $\langle s(a) \rangle \setminus \{0\}$은 벡터 공간으로써의 성질을 고려하면 조건 1을 만족함을 알 수 있다.

조건 3: $2y \in \langle s(a) \rangle \setminus \{0\}$이면 $y < 2^{1000}$이다. 어떤 $c_i \in \{0, 1\}$가 유일하게 존재하여 $2y = \bigoplus_{i = 0}^{1001 - (d - 1)} c_i 2^i a$ 이다. 이때 좌변은 짝수이므로 $c_0 = 0$이다. 따라서 $y = \bigoplus_{i = 1}^{1001 - (d - 1)} c_i 2^{i - 1} a \in \langle s(a) \rangle$이다. $y \neq 0$이므로 $y \in \langle s(a) \rangle$이다.

조건 2: $y \in \langle s(a) \rangle \setminus \{0\}$이고 $y < 2^{1000}$이라고 하자. 어떤 $c_i \in \{0, 1\}$가 유일하게 존재하여 $y = \bigoplus_{i = 0}^{1001 - (d - 1)} c_i 2^i a$ 이다. 이때 $y$의 이진 전개에서 $2^{1000}$자리 수는 0이고, 따라서 $c_{1001 - (d - 1)} = 0$이다. $2y = \bigoplus_{i = 0}^{1000 - (d - 1)} c_i 2^{i + 1} a$이고, $2y \neq 0$이므로 $2y \in \langle s(a) \rangle$이다.

따라서 $f(\{a\}) \subset \langle s(a) \rangle \setminus \{0\}$이다. 한편, 조건 2, 3에 의해 $s(a) \subset f(\{a\})$이고, 조건 1에 의해 $f(\{a\})$는 $\oplus$에 대해 닫혀있다. 따라서 $f(\{a\}) \cup \{0\}$는 선형공간이고, $\langle s(a) \rangle$을 포함한다. 따라서 $f(\{a\}) = \langle s(a) \rangle \setminus \{0\}$이다.

$a = a_{d - 1} a_{d - 2} \cdots a_1 a_0$이라고 하자. $\mathbb{Z}_2^{d - 1}$를 $2^0, 2^1, \cdots, 2^{d - 2}$으로 생성되는 부분공간이라고 하면, 이는 이진 전개의 길이가 $d - 1$ 이하인 모든 수들의 집합과 같다. 따라서 $V_S \cap \mathbb{Z}_2^{d - 1} = 0$이다. 한편 임의로 주어진 $c_{d - 1}, c_d, \cdots, c_{1000} \in \{0, 1\}$에 대해 $c_{1000} c_{999} \cdots c_{d - 1} x_{d - 2} x_{d - 3} \cdots x_1 x_0 \in \langle s(a) \rangle \subset V_S$ 을 만족하는 $x_0, x_1, \cdots, x_{d - 2}$를 항상 찾을 수 있다. 따라서 $0 \to \mathbb{Z}_2^{d - 1} \hookrightarrow \mathbb{Z}_2^{1001} \twoheadrightarrow V_S \to 0$ 는 완전열이고, 계수-퇴화차수 정리로부터 $\dim \mathbb{Z}_2^{d - 1} + \dim V_S = \dim \mathbb{Z}_2^{1001}$이다. 한편 $s(a)$의 크기는 $1001 - (d - 1)$이므로, $\dim V_S = 1001 - (d - 1) = \dim \langle s(a) \rangle$이고 $V_S = \langle s(a) \rangle$이다. 따라서 $f(\{a\}) = \langle \{a\} \rangle \setminus \{0\} = V_S \setminus \{0\} = f(S)$ 를 얻는다.

풀이

두 양의 정수 $x, y < 2^{1000}$에 대해, $x \otimes y$를 $f(\{x, y\})$에 포함된 가장 작은 정수로 정의하자. 이는 다항식에서의 유클리드 호제법을 응용하여 계산할 수 있고, $x, y$가 작다면 빠르게 계산된다. $x \otimes y \le \min \{x, y\}$를 정의로부터 알 수 있는데, 문제에서 모든 $a_i$이 $2^{30}$보다 작으므로 풀이에서 사용할 $x \otimes y$ 계산은 모두 상수 시간 복잡도로 계산할 수 있다. 양의 정수 $x, y, z < 2^{1000}$에 대해, $(x \otimes y) \otimes z = x \otimes (y \otimes z),$ $x \otimes y = y \otimes x,$ $x \otimes x = x$ 를 관찰하자. 첫 번째 등식은 $f(f(\{x, y\}) \cup \{z\}) = f(\{x, y, z\}) = f(\{x\} \cup f(\{y, z\}))$이므로 성립한다. 주어진 나무에서 적당히 뿌리를 정하고, 각 정점에 대해 $2^k$번째 조상과 그 정점에서 $2^k$번째 조상까지 가는 경로에 놓인 모든 $a_i$를 $\otimes$하는 sparse table을 만들 수 있다. 특히 $\otimes$는 $x \otimes x = x$와 같이 idempotent한 성질 덕분에 sparse table을 만들 때 뿌리에서 더 올라가려고 하는 것에 대해 어떤 예외 처리를 하지 않아도 되어 간편하다. 만들어낸 sparse table을 이용하여 각 쿼리에 대해 lca를 이용해 최단경로를 찾아내면서 그 경로의 모든 $a_i$를 $\otimes$한 값을 $\mathcal{O}(\log n)$의 시간 복잡도로 구할 수 있다.