2025. 7. 31. 02:14ㆍDiamond/Diamond II
내가 살다살다 이런 토픽을 가진 문제를 볼 거라고는 예상하지 못했다. 출제자가 예상한 풀이법이 무엇인지는 모르겠지만 장담하건대 내 풀이법이 가장 생각하기 쉬울 것이다. 아니라면, 부디 연락해 달라. ta.nflight11@gmail.com으로 상세한 풀이과정을 주면 된다.
물론 내 풀이법도 쉽지는 않다. 이게 대체 뭐야 싶은 것이기도 하고... Modular form을 배우고 있지 않았다면 못 풀었을 거다. 이게 뭔 상관이냐고? 풀이를 보라.
그럼 본격적으로 풀이에 돌입해 보자.
문제
당신은 \(a,b\)로만 구성된 문자열 \(s\)을 가지고 있다. 문자열의 어느 위치에서나 \(aa, bbb, ababab\)를 끼워넣거나 지우는 연산을 0회 이상, 순서 상관 없이 원하는 만큼 수행할 수 있다.
당신의 목표는 이러한 연산을 통해 초기 문자열 \(s\)로부터 얻을 수 있는 길이 \(x\)인 문자열의 갯수를 계산하는 것이다. 답이 매우 커질 수 있으므로, \(998\,244\,353\)으로 나눈 나머지를 대신 구해도 좋다.
입력
첫 번째 줄에 문자열 \(s\)의 길이를 나타내는 정수 \(N\)이, 두 번째 줄에 문자열 \(s\)가, 세 번째 줄에 정수 \(x\)가 주어진다. \((1\le n\le 300\,000;\) \(0\le x\le 10^9)\)
예제 입력)
# 예제 입력 1
6
ababab
3
# 예제 입력 2
3
bbb
2
# 예제 입력 3
5
babab
35
출력
문자열 \(s\)에 0회 이상의 연산을 수행하여 얻을 수 있는 길이 \(x\)의 문자열 갯수를 \(998\,244\,353\)으로 나눈 나머지를 출력한다.
예제 출력)
# 예제 출력 1
1
# 예제 출력 2
1
# 예제 출력 3
866826000
내 코드
# -not included-
고난이도 문제이기도 하고, 코드는 그닥 중요하지 않아서 생략한다. 풀이를 이해하는 과정이 구현하는 과정보다 훨씬 고통스러울 것이다. 거의 모든 사람에게 그럴 것이다...
우선 행렬을 생각하자.
\[\sigma=\begin{bmatrix}0&-1\\1&0\end{bmatrix}, \tau=\begin{bmatrix}1&1\\0&1\end{bmatrix}\]
이 두 행렬은 \(\sigma^2=-I=(\sigma\tau)^3,\tau^n=\begin{bmatrix}1&n\\0&1\end{bmatrix}\)라는 기묘한 성질을 만족한다. 이를 검증하는 것은 매우 쉬우니 직접 해 보라. 또한 행렬식이 \(1\)이고, 따라서 이를 통해 \(\sigma,\tau\in\text{SL}_2(\mathbb Z)\)임을 확인할 수 있다. 또한 이 두 행렬이 \(\text{SL}_2(\mathbb Z)\)의 generator임은 매우 잘 알려져 있는 사실이다. 모른다고? 받아들여야 한다. 증명은 쉽지 않다. 이건 모든 \(\text{SL}_2(\mathbb Z)\)의 원소, 즉 모든 성분이 정수이고 행렬식이 1인 \(2\times 2\) 행렬은 반드시 \(\sigma,\tau\)의 곱으로 표현 가능하다는 것이다.
그런데 \(\sigma^2=-I=(\sigma\tau)^3\)이라는 성질은 문제에서 주어진 연산에서 본 것 같지 않은가? 빈 문자열을 행렬에 대응시키면 (곱해도 변하지 않아야 하므로) 당연히 \(I\)여야 할 것이다... 그러면 \(I=-I\)로 취급해 보는 것은 어떨까? \(Z=\{I,-I\}\)는 \(\text{SL}_2(\mathbb Z)\)의 부분군이고, 당연하지만 normal subgroup이다. 그러니 \(\mod Z\)를 취해버리면 \(\sigma^2=I=(\sigma\tau)^3\)이라고 취급할 수 있다는 거다. 어디에서? \(\text{SL}_2(\mathbb Z)/Z\)에서. 이를 수학자들은 간단하게 \(\text{PSL}_2(\mathbb Z)\)라고 표기한다. Projective special linear group의 두문자인데, 이것까지는 몰라도 된다.
이제 \(a=\sigma, b=\tau\)라고 보자. 그렇다면 문제의 연산에 군의 성질이 부합하기 위해서는 \(\tau^3=I\pmod Z\)라는 것까지 만족해야 한다. 이는 행렬의 성분을 \(\mathbb Z\)가 아니라 \(\mathbb Z/3\mathbb Z\)라고 둠으로서 쉽게 달성 가능하다. \(\mathbb Z/3\mathbb Z\)의 세계에서는 \(3=0\)이기 때문이다. 물론 성분을 \(\mathbb Z\)에서 \(\mathbb Z/3\mathbb Z\)로 바꾼다고 하더라도 \(\sigma,\tau\)가 generator라는 사실은 바뀌지 않는다. 그러므로 유한 번의 연산을 통해 변형 가능한 서로 다른 두 문자열을 같은 것으로 취급하면, 그것은 \(G=\text{PSL}_2(\mathbb Z/3\mathbb Z)\)와 같다. 즉 우리가 해야 하는 것은 \(\sigma,\tau\)를 \(x\)번 곱한 문자열 중 주어진 문자열 \(s\)와 같은 \(G\)의 원소의 갯수를 세는 것으로 귀결된다.
이렇게 장황한 이야기로 \(G\)를 끌어낸 이유는 이 군이 유한군이기 때문이다. 이건 당연한 이야기이다. 일단 \(2\times 2\)의 행렬 중 성분이 \(0,1,2\) 중 하나인 것들 \(81\)개보다는 확실히 적을 테니까. 코드를 짜서 조건을 만족시키는 모든 행렬을 검사한 뒤 \(A, -A\)를 같은 것으로 취급해 본다면 갯수가 \(12\)개밖에 안 된다는 사실을 알 수 있다!
왼쪽에(혹은 오른쪽에) \(\sigma, \tau\)를 곱하는 것은 이 정점 \(12\)개 간에 유향 간선을 \(A\mapsto\sigma A,\tau A\)의 형태로 긋는 것과 같다. \(s\)이 \(12\)개의 정점 중 무엇인지 아는 것 역시 \(I\)에 순서대로 행렬을 곱하는 것으로 알 수 있고 이는 \(\mathcal O(N)\) 정도가 소모된다. 길이 \(x\)인 문자열은 정점 \(12\)개, 간선 \(24\)개의 매우 작은 그래프에서 빈 문자열인 \(I\)에서 출발해 간선을 \(x\)회 타는 것으로 해석할 수 있고, 이는 인접 행렬에 분할 정복을 이용한 거듭제곱으로 \(\mathcal O(12^3\log_2 x)\) 정도가 소요된다.
그러니 이 모든 과정은 \(\mathcal O(N+12^3\log_2 x)\) 안에 수행할 수 있다. 충분하다 못해 남아도는 시간이고, 그 느린 파이썬에서도 기본 시간에서 오차 정도인 4~8ms 정도만 더 먹는다.
이 전체 과정은 사실 representation theory의 한 과정이고, relation(이 문제에서는 \(a^2=b^3=(ab)^3=1\))로부터 군의 형태를 끌어오는 것은 대단히 어렵고, 일반적으로 불가능하며, 이 군이 유한군인지도 가늠할 수가 없다. 예를 들어 generator가 \(x,y,z\)이고 \(z=xyx^{-1}y^{-1},xz=zx,yz=zy\)의 relation을 가진 군은 discrete Heisenberg group \(\text{H}_3(\mathbb Z):=\left\{\begin{bmatrix}1&a&b\\0&1&c\\0&0&1\end{bmatrix}:a,b,c\in\mathbb{Z}\right\}\)이다. 예상할 수 있겠는가? 증명할 수는? 원소의 수가 무한임을 이렇게 직접 찾아내지 않고 증명할 수 있겠는가?
문제의 제목과 같이, 충분한 Knowledge가 있어야 풀 수 있는 문제였다.
이로서 18457번의 풀이를 마친다.
