BOJ 32148 - 무한평면 색칠하기
고3이라 바빠서 글 올리기로 해놓고 제대로 올리지도 못했습니다… 수능 끝나면 좀 더 열심히 해 보겠습니다
| 시간 제한 | 메모리 제한 |
|---|---|
| 2 초 | 1024 MB |
문제
모든 격자점이 흰색으로 칠해진 좌표평면이 있다. 지호는 서 있는 점에서 $(x_i, y_i)$만큼 혹은 $(-x_i, -y_i)$만큼 움직일 수 있다.
이때, 지호가 원점 $(0, 0)$에서 출발해서 도달할 수 있는 점을 모두 검은색으로 칠하자.
예를 들어, $(2,0)$, $(2,2)$, $(0,2)$만큼 이동할 수 있는 경우 다음과 같다.
빨간 점은 원점, 파란 점은 원점에서 바로 이동할 수 있는 점이다.
$(-x_i, -y_i)$만큼 이동하는 것이 가능하므로, 녹색 점 또한 원점에서 바로 이동할 수 있는 점이다. 이외에 여러 번 이동해서 도달할 수 있는 점은 검은색으로 칠해져 있다. 이때, 흰색으로 칠해진 점을 제외하고는 모두 원점에서 도달할 수 있다.
이렇게 하면, 모든 격자점 중 칠해진 점의 비율을 유리수로 나타낼 수 있다. 위 예시에서는 좌푯값이 모두 짝수인 점만 칠해지므로 칠해진 점의 비율은 $1/4$이다.
이 유리수를 기약분수 형태로 나타내면 $\frac{a}{b}$라 할 때, $(a \cdot b^{-1}) \bmod 1\,000\,000\,007$을 출력하여라. 이때 $1\,000\,000\,007$은 소수이다.
단, 비율이 $0$인 경우 $0$을, $1$인 경우 $1$을 출력하면 된다. 비율을 항상 유리수로 나타낼 수 있고, 이를 기약분수로 나타낸 형태 $\frac{a}{b}$에 대해 $b$가 $1\,000\,000\,007$의 배수인 테스트케이스는 주어지지 않는다. 즉, 답이 항상 존재함을 보장한다.
입력
첫 번째 줄에 $N$이 주어진다.
두 번째 줄부터 $N$개의 줄 중 $i$번째 줄에 $x_i, y_i$가 공백으로 구분되어 주어진다.
출력
첫 번째 줄에 문제의 답을 출력하여라.
제한
- $2 \leq N \leq 1\,000\,000$
- $-10^9 \leq x_i, y_i \leq 10^9$ ($1 \leq i \leq N$)
풀게 된 계기
나는코더다 2024 반년대회 H번이었고, 다른 문제들을 대충 훑어보고 어차피 3솔은 못 할 거 같은데 재미있어보이는 문제를 잡았습니다. 결국 대회 중에는 ABC를 치러 갔다 오느라 못 풀었는데, 90%가량 풀어 둬서 ABC가 없었으면 풀었을 거 같아 아쉽습니다. 그렇지만 생애 첫 ABC 블루퍼포를 받았기 때문에 그걸로 만족합니다.
풀이 과정
먼저 문제를 1차원에서 생각해 보았습니다. $a_1, a_2, …$만큼 움직일 수 있다면 움직일 수 있는 점들은 $\gcd(a_1, a_2, …)$의 배수인 점들일 것입니다. 따라서 2차원상에서도 무언가 gcd와 관련되겠다… 는 추측할 수 있었습니다.
처음엔 뭔가 x좌표와 y좌표만 가지고 열심히 해 보려 했습니다… 만 틀렸습니다만 받았을 뿐 유의미한 결과를 내지 못했습니다. 그러던 중 떠오른 아이디어는 이 문제의 조건을 만족하는 점들의 집합은 격자점 위에서의 평행사변형 타일링의 꼭짓점이 된다는 것입니다. 말로만 들으면 어렵게 느껴질지도 모르지만, 어려운 얘기는 아닙니다.
이런 모양을 이룬다는 이야기입니다.
이러한 모양을 어떻게 나타낼 수 있을까요? 여러 방법을 사용할 수 있겠지만 (그리고 그 방법에 따라 풀이의 난이도 혹은 완성도가 달라지겠지만 - 저는 그렇게 깔끔한 방법을 사용한 건지는 잘 모르겠어요) 저는 세 개의 변수, $a, b, k$를 사용하는 방법을 택했습니다. 각각의 변수가 무엇을 의미하는지는 아래에서 설명하도록 하겠습니다.
문제를 단순화시켜, 가능한 이동이 두 개의 순서쌍 $(x_1, y_1), (x_2, y_2)$로만 이루어져있다고 생각합시다.
먼저, 도달할 수 있는 격자점의 x좌표를 구하는 것은 처음에 말했던 1차원상의 문제와 동일합니다. 이때 $\gcd(x1, x2) = g$라고 하겠습니다. 이번에는 y좌표에 대해 생각해볼 것인데, 대신 x좌표를 고정해 놓고 해당 x좌표에서 도달할 수 있는 y좌표에 대해 생각해보겠습니다.
주어진 입력에 대해 도달할 수 있는 모든 점은 $(x_1n + x_2m, y_1n + y_2m)$꼴로 표현할 수 있습니다. 이때 어떤 한 점 $(p, q)$가 도달 가능하다면, $(p + x_1n + x_2m, q + y_1n + y_2m)$ 꼴로 나타내어지는 점들 역시 도달 가능합니다. 이때 x좌표를 고정시켜놓았으므로, $x_1n + x_2m = 0$이 됩니다. 따라서 $n = \dfrac{k}{x_1}, m = -\dfrac{k}{x_2}$꼴이 되고 $n, m$이 정수이므로 $k = \text{lcm}(x_1, x_2) \cdot k’$로 정리하면
$n = \dfrac{\text{lcm}(x_1, x_2) \cdot k’}{x_1} = \dfrac{x_2 k’}{g}, m = -\dfrac{\text{lcm}(x_1, x_2) \cdot k}{x_2} = -\dfrac{x_1 k’}{g}$가 됩니다.
따라서 이 식을 y좌표에 대해 정리해주면, $q + y_1n + y_2m = q + \dfrac{x_2 y_1 k’}{g} - \dfrac{x_1 y_2 k’}{g} = q + \dfrac{x_2 y_1 - x_1 y_2}{g} k’$가 됩니다.
이번엔 x좌표가 $g$만큼 변할 때 y좌표가 어떻게 변하는지 살펴봅시다. 위에서 x좌표가 고정되었을 때 가능한 y좌표들을 구했으므로, 우리는 하나의 y좌표만 구하면 (일종의 합동식 느낌으로) 다른 y좌표들을 모두 구할 수 있습니다. 이를 위해 확장 유클리드 호제법을 사용할 수 있습니다. 확장 유클리드를 통해 $x_1z + x_2t = g$인 $z, t$를 구할 수 있고, 이번에도 역시나 $(p, q)$가 도달 가능하다고 하면 $(p + x_1z + x_2t, q + y_1z + y_2t)$ 역시 도달 가능합니다. 따라서 x좌표가 $g$만큼 변할 때 $y$좌표는 $y_1z + y_2t$만큼 변한다고 나타낼 수 있습니다.
위를 종합해서 나타내면, 도달 가능한 모든 점들은 어떤 두 정수 $n, m$에 대해 $(gn, y_1z + y_2t + \dfrac{x_2 y_1 - x_2 y_2}{g}m)$으로 나타낼 수 있습니다. 여기서 $g = a, y_1z + y_2t = b, \dfrac{x_2 y_1 - x_1 y_2}{g} = k$로 나타내 정리하면, 위의 식을 $(an, bn + km)$으로 간략화해서 표기할 수 있습니다.
이제 $(an, bn)$과 $(0, km)$을 따로 생각해보겠습니다. 여기서 $(an, bn)$은 원점에서 $(a, b)$의 이동으로 이동할 수 있는 점들이라고 생각할 수 있습니다. 이제 여기에 또 다른 이동 $(x_2, y_2)$를 추가한다고 가정하면, $(a, b)$와 $(x_2, y_2)$로 이동할 수 있는 점들의 집합을 어떤 두 정수 $n’, m’$에 대해 $(a’n’, b’n’ + k’m’)$으로 나타낼 수 있습니다. 이걸 다시 $(a’n’, b’n’)$와 $(0, k’m’)$로 분리해서 생각해 봅시다. 그럼 $(0, km)$과 $(0, k’m’)$로 도달 가능한 점들은 다시 어떤 정수 ${m’’}$에 대하여 $(0, \gcd(k, k’)m’’)$로 나타낼 수 있습니다. 같은 형태가 보이시나요? 이제 이걸 모든 입력에 대해서 수행해주면 답을 얻을 수 있습니다! 각각의 과정은 확장 유클리드 등만 사용하므로 로그 시간에 수행할 수 있습니다.
이제 (간략히 설명하면) $x$축 상에서의 밀도는 $1/a$, $y$축 상에서의 밀도는 $1/k$이므로 $(ak)^{-1} \bmod 1000000007$이 구하려는 답이 됩니다.
참고사항
$b$를 구하는 과정에서 매번 곱셈을 수행하므로 수가 과도하게 커질 수 있습니다. 어차피 y좌표는 $b$와 $k$의 선형 결합으로 나타내므로 $b$ 대신 $b \bmod k$를 사용해도 문제없습니다. 대신 $k = 0$인 경우만 주의해주시면 됩니다.
더 깔끔한 풀이가 떠오르면 글을 하나 더 올릴 수도 있을 것 같은데, 제 지식으로 그게 될지는 모르곘습니다 평행사변형을 행렬로 나타낸 다음 2x2 행렬의 행렬식이랑 어떻게 해서 풀 수 있을 것 같은데…