랜덤 소트
시간 제한2초메모리 제한128 MB
크기가 최대 8인 순열에서 무작위로 역전 쌍을 골라 교환하여 정렬이 완료될 때까지 필요한 기대 교환 횟수를 구하는 문제입니다.
문제
랜덤 소트는 순열에서 i < j이고 A[i] > A[j]인 위치 쌍을 하나 무작위로 골라 두 원소를 서로 바꾸는 정렬 과정이다.
주어진 순열이 오름차순으로 정렬될 때까지 필요한 교환 횟수의 기댓값을 구하라.
입력
첫째 줄에 순열의 크기 N이 주어진다. 둘째 줄에 순열을 이루는 N개의 정수가 주어진다.
각 정수는 1 이상 N 이하이며, 같은 정수는 두 번 이상 주어지지 않는다. N은 8 이하의 자연수이다.
출력
필요한 교환 횟수의 기댓값을 출력한다. 정답과의 절대 또는 상대 오차가 10^-6 이하이면 정답으로 인정된다.