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

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

18542번: Permutant

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

$$\left[\begin{array}{ccc}0& 1& 0\\ 0& 0& 1\\ 1& 0& 0\end{array}\right]$$

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

$$detP=det\left[\begin{array}{ccccc}v& Av& A^{2}v& \cdots & A^{n-1}v\end{array}\right]$$

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

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

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

$$AB=BA,B{v}_1=e_1,detB\ne 0$$

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

$$det\left[\begin{array}{cccc}v& Av& \cdots & A^{n-1}v\end{array}\right]=det{B}^{-1}detB\left[\begin{array}{cccc}v& Av& \cdots & A^{n-1}v\end{array}\right]=$$

$$det{B}^{-1}det\left[\begin{array}{cccc}Bv& ABv& \cdots & A^{n-1}Bv\end{array}\right]=det{B}^{-1}det\left[\begin{array}{cccc}{e}_1& A{e}_1& \cdots & A^{n-1}{e}_1\end{array}\right]$$

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

$$A=Q{D}_A{Q}^{-1}$$

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

$$(B{v}_1=e_1)\to (D_B(Q^{-1}{v}_1)=(Q^{-1}{e}_1))$$

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

$$\left[\begin{array}{ccc}{d}_1& \cdots & 0\\ ⋮& \ddots & ⋮\\ 0& \cdots & d_n\end{array}\right]\left[\begin{array}{c}{x}_1\\ ⋮\\ x_n\end{array}\right]=\left[\begin{array}{c}{y}_1\\ ⋮\\ y_n\end{array}\right]⟹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는

$$\left[\begin{array}{cccc}0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\\ 1& 0& 0& 0\end{array}\right]$$

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

$$Q=\frac{1}{4}\left[\begin{array}{cccc}1& 1& 1& 1\\ 1& i& -1& -i\\ 1& -1& 1& -1\\ 1& -i& -1& i\end{array}\right]$$

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

$${\left[\begin{array}{cccc}1& 1& \cdots & 1\end{array}\right]}^t$$

이다. 후자는 약간 복잡하다. $v1={\left[\begin{array}{cccc}{a}_1& a_2& \cdots & a_n\end{array}\right]}^t$로 놓고, 다항식 f(x)를

$$a_1+a_{2}x+a_3{x}^2+\cdots$$

로 놓으면, 

$$det\left[\begin{array}{cccc}v& Av& \cdots & A^{n-1}v\end{array}\right]=\prod _{r^n=1}^{}f(r)$$

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

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

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

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

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

 

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