[CodeForces] Square Root of Permutation : 순열 제곱근

목차

• Square Root of Permutation
  • 문제 설명
  • Solution
  • Code

문제 설명

문제 : 코드포스 Educational Round 4, E번, Square Root of Permutation

길이 n의 순열이란 1부터 n까지의 정수를 한 번씩만 포함하는 배열이다.
예를 들어 q = [4, 5, 1, 2, 3]는 순열이다.

순열의 제곱 p란 순열 q에 대해서 p[i] = q[q[i]]를 의미한다.
예를 들어 q = [4, 5, 1, 2, 3] 일 때

p[1] = q[q[1]] = q[4] = 2
p[2] = q[q[2]] = q[5] = 3
p[3] = q[q[3]] = q[1] = 4
p[4] = q[q[4]] = q[2] = 5
p[5] = q[q[5]] = q[3] = 1

p = = [2, 3, 4, 5, 1] 이다.

이제 어떤 순열의 p가 주어질 때 이 순열의 제곱근(Square Root of Permutation) q를 구해야한다.

Solution

1. 주어진 순열에서 사이클 집합을 모두 찾는다.

예시. 순열 p = [4, 5, 1, 2, 3]은 아래 그림1과 같은 사이클을 갖는다.

그림1

예시. 순열 p = [3, 4, 5, 2, 1]은 아래 그림2과 같은 두 사이클을 갖는다.

그림2

2. 사이클의 길이가 홀수인지 짝수인지에 따라 다른 방법으로 순열 제곱근(Square Root of Permutation)을 구한다.

사이클 길이가 홀수 일때

홀수 길이의 사이클을 제곱하면 같은 길이의 홀수 사이클을 얻는다. 아래 그림3을 보고 확인할 수 있다. 왼쪽이 원래 사이클, 오른쪽이 제곱했을 때 사이클을 나타낸다.

그림3

여기서 직관적으로 홀수 길이의 사이클의 제곱근으로 같은 길이의 홀수 사이클이 존재한다는 것을 알 수 있다. 즉 사이클 의 길이가 2k+1이면 사이클 의 길이도 2k+1이다.

길이가 2k+1인 사이클 에서 길이의 거의 절반인 k+1회 이동하면 입장에서 2k+2회를 이동한 것이다. 즉 한 바퀴를 다 돌고 한 번 더 간것이기 때문에 입장에서 을 에 대응시킨 것이 입장에서 을 에 대응시킨 것이다.

이 성질을 이용해서 이 있을 때 순열 제곱근의 사이클 을 구할 수 있다.

사이클 길이가 짝수 일때

길이가 2*k (k는 양의 정수)인 사이클의 원소는 순열을 제곱했을때 독립적인 길이 k의 두 사이클을 이룬다.

이 사실은 아래 그림4을 통해서 직관적으로 알 수 있다. 왼쪽의 사이클이 제곱됐을때 나타나는 두 독립적인 사이클을 나타냈다.

그림4

이 사실로 부터 제곱 순열에서 길이가 짝수인 두 쌍의 사이클 이 있을 때 순열 제곱근의 사이클 을 구할 수 있다.

만약 같은 짝수 길이의 사이클이 쌍으로 존재하지 않는다면 제곱근 순열은 존재하지 않는다.

Code