-
koosaga.com/264 이 글을 보고 풀 수 있었다
주어지는 순열을 PER이라고 할 때 Cyclic Shift를 만족하는 행렬 C의 첫 행의 원소 P를 다음과 같이 구할 수 있다
- 순열의 인덱스를 저장하는 배열 SEQ를 선언하고 $SEQ[PER[i] - 1] = i$로 배열에 원소를 담는다
- 바뀐 순열의 인덱스를 담는 배열 PATH를 선언하는데 이 배열의 첫 번째 원소는 0이 되므로 배열 접근은 $N-1$번만 하면 된다
- PATH의 원소는 SEQ와 이전항을 이용해 구할 수 있다
- 주어진 수열을 A라고 하면 i번째 PATH의 원소를 갱신하면서 P도 $P[i]=A[PATH[i]]$과 같이 갱신해준다
이렇게 구한 P를 이용해 $Resultant(P(x), x^n-1)$를 구해주면 AC를 받을 수 있다
