[백준 18542] Permutant (Ruby III) 풀이

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

18542번: Permutant

 먼저 주어진 Permutation는 Linear Transform의 일종임을 파악해야 한다. 예를 들어, Permutation {1, 2, 3} -> {3, 1, 2}는

$$ \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix} $$

로 나타낼 수 있다. 따라서 해당 Linear Transform을 행렬 A로 놓아도 무방하며, 구하고자 하는 식은

$$ \det P = \det \begin{bmatrix} v & Av & A^2v & \cdots & A^{n-1}v \end{bmatrix} $$

으로 쓸 수 있다. 이 행렬에 적당한 transform을 가해, 주어진 행렬을 determinant 계산이 편한 형태로 바꾸고 싶다. 예컨대 v가 e1이었다면, v에 연산 A를 몇 번 적용하든 그 값은 standard unit vector e_i일 것이다. 그렇다면 주어진 행렬의 행렬식은

1. permutation이 더 작은 순열 사이클로 분할되면 0
2. permutation이 더 작은 순열 사이클로 분할되지 않으면 1 또는 -1

임이 자명하다. 따라서 우리는

$$ AB = BA, Bv_1 = e_1, \det B \ne 0 $$

인 행렬 B를 찾도록 한다. 그러한 행렬 B를 찾으면 다음과 같은 결과를 얻어낼 수 있기 때문이다.

$$ \det \begin{bmatrix} v & Av & \cdots & A^{n-1}v \end{bmatrix} = \det B^{-1} \det B \begin{bmatrix} v & Av & \cdots & A^{n-1}v \end{bmatrix} = $$

$$ \det B^{-1} \det \begin{bmatrix} Bv & ABv & \cdots & A^{n-1}Bv \end{bmatrix} = \det B^{-1} \det \begin{bmatrix} e_1 & Ae_1 & \cdots & A^{n-1}e_1 \end{bmatrix} $$

조건이 많아 그러한 행렬을 찾기가 까다로운 것처럼 느껴질 수도 있겠지만, 결론만 말하자면 그런 행렬 B를 찾는 것은 가능하다. 일단 A는 언제나 대각화 가능하다는 사실을 알 수 있다. A가 유니타리 행렬이기 때문이다. 이는 자명한 사실인데 A의 아무 두 행벡터나 골라서 스칼라곱을 취하면 언제나 0(두 행이 다를 때) 또는 1(같을 때)이 나온다는 사실을 알 수 있다. 따라서 A는 정칙행렬이므로 대각화 가능하고, 나아가 A의 대각성분들은 그 절댓값이 언제나 1이라는 사실도 알 수 있다. 그러면 이제 A를

$$ A = QD_A Q^{-1} $$

이라고 쓰는 게 가능하다. 한편 두 행렬이 대각화 가능하면, 두 행렬 사이에 곱에 대한 교환법칙이 성립할 필요충분조건은 어떤 basis-change 행렬 Q에 대해 두 행렬이 동시에 대각화되는 것이므로, \( B = QD_B Q^{-1} \)가 성립한다. 그렇다면 두 번째 조건을 약간 수정하여

$$ (Bv_1 = e_1) \rightarrow (D_B(Q^{-1} v_1) = (Q^{-1} e_1)) $$

라고 쓸 수 있다. 꽤 복잡해 보이는 방정식이지만, 뜯어보면 그냥 n개의 일차방정식 쌍이라는 것을 알 수 있다! 왜냐하면 D가 대각행렬이기에 다음 사실이 성립하기 때문이다.

$$ \begin{bmatrix} d_1 & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & d_n \end{bmatrix} \begin{bmatrix} x_1 \\ \vdots \\ x_n \end{bmatrix} = \begin{bmatrix} y_1 \\ \vdots \\ y_n \end{bmatrix} \Longrightarrow d_i = y_i / x_i $$

깔끔하다. v_1과 e_1은 이미 주어져 있으므로 우리는 Q^-1에 대해서만 알면 된다. 그런데 A의 characteristic polynomial은 꽤나 구해주기가 쉽다. 순열의 성질에 의해, A^p = I가 되게 하는 자연수 p가 항상 존재하기 때문이다! 다시 말해 A의 고유치는 항상 1의 제곱근이어야 하는 상황. 먼저 간단한 경우로, p=n인 경우를 생각해볼 수 있다. 다시 말해, A를 대표하는 permutation이 더 작은 sub-permutation으로 분할되지 않는 상황. 예시로 주어진 permutation이 {1, 2, 3, 4} -> {4, 1, 2, 3}일 때, A는

$$ \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{bmatrix} $$

이다. 이 행렬의 특성다항식이 t^4 - 1이므로, 고유치는 1, -1, i, -i이고 이들 각각에 해당하는 고유벡터를 일일이 찾아주면 된다. 그런데 이것은 그냥 고유벡터의 정의에 때려박으면 나온다!

$$ Q = {1 \over 4} \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end{bmatrix} $$

규칙이 보이지 않는가? 그렇다. 그냥 1의 제곱근들을 순서대로 나열하면 된다... 한편, 간단한 계산을 통해 Q^2 = 1/4 I를 얻는데 다시 말하면 Q의 역행렬은 4Q와 같다는 것이다. 이제 Q^-1을 구했으므로, \( Q^{-1} e_1 , Q^{-1} v_1 \)만 구해주면 된다. 먼저, 전자는 자명히 

$$ \begin{bmatrix} 1 & 1 & \cdots & 1 \end{bmatrix}^t $$

이다. 후자는 약간 복잡하다. \( v1 = \begin{bmatrix} a_1 & a_2 & \cdots & a_n \end{bmatrix}^t \)로 놓고, 다항식 f(x)를

$$ a_1 + a_2 x + a_3 x^2 + \cdots $$

로 놓으면, 

$$ \det \begin{bmatrix} v & Av & \cdots & A^{n-1}v \end{bmatrix} = \prod_{r^n=1}^{} f(r) $$

을 얻는다! 참으로 아름다운 결론이 아닌가? 이 결론을 보면, permutation이 간단해서 답도 간단하게 나오는 건 아닐지 궁금해할 수 있는데, 사실은 permutation이 좀 더 복잡해도 답이 간단하게 나온다. 왜 그런지, 보다 일반적인 예시를 살펴보자.

1. A를 대표하는 permutation이 더 간단한 permutation으로 분할되지 않을 때

이 경우에는 위에서 얻었던 식과 부호만 차이나는 결과를 얻는다. 왜냐하면 이런 형태의 모든 행렬은 닮음이기 때문이다. 적절한 basis change를 통해 A를 저 위의 행렬 꼴로 바꿔주면, 모종의 대칭성이 작용하여 구하고자 하는 행렬의 행렬식이 똑같이 나온다는 것을 알 수 있다. 따라서 위의 식과 똑같이 계산해 주면 되나, \( \det \begin{bmatrix} e_1 & Ae_1 & \cdots & A^{n-1}e_1 \end{bmatrix} \)이 1이 아니라 -1일 수도 있다는 것을 감안해서 식을 보정해주어야 한다.

2. 더 간단한 permutation으로 분할될 때

A의 고유벡터 중 성분이 0인 벡터가 있게 된다. 그 열벡터를 Q의 제1행으로 놓으면, 대각행렬의 대각성분에 0이 포함되어 있으므로 det은 그냥 0이다(...).

 

결국 마지막으로 해 줄 일은 저 간단해 보이는 식을 계산해서 거기에 1을 곱하든 -1을 곱하든 해서 정답을 내는 일이다. 그러나 저 식을 naive하게 계산하면 안 된다. 시간복잡도 O(n^2) 안에 안 들어온다. 그래서 알아야 할 개념이 Resultant(종결식)다. 저 위키백과 문서를 읽고 종결식 계산하는 프로그램을 구현하면 O(n^2) 안에 들어오면서 AC를 받을 수 있다.