시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 6 4 3 60.000%

문제

강호는 N명의 친구들을 파티에 초대하려고 한다. 강호의 친구들은 0번부터 N-1번까지 번호가 매겨져 있다.

강호의 친구들은 최대 1명의 친구를 싫어한다. i번 친구가 싫어하는 친구는 A[i]로 주어지며, A[i]가 i와 같은 경우에는 싫어하는 친구가 없는 경우이다.

강호는 친구들을 한 번에 한 명씩 초대를 할 것이다. i번 친구를 초대했을 때, A[i]가 초대를 거부했거나, 아직 A[i]에게 초대를 하지 않은 경우에만 i번 친구가 초대를 승낙한다. 즉, A[i]가 강호의 초대를 거절한 경우나 아직 A[i]에게 초대를 하지 않은 경우이다.

친구를 초대하는 순서에 따라서, 초대를 승낙하는 친구의 수가 달라진다. 따라서, 강호는 친구를 랜덤한 순서로 초대하기로 결정했다. (각각의 순열이 선택될 확률은 모두 같다)

강호의 초대를 승낙할 친구의 기댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 친구의 수 N (1 ≤ N ≤ 50)이 주어진다.

둘째 줄에는 i번 친구가 싫어하는 친구 A[i]가 주어진다. (0 ≤ A[i] ≤ N-1)

출력

강호의 초대를 승낙할 친구의 기댓값을 출력한다. 정답과의 절대/상대 오차는 10-9까지 허용한다.

예제 입력

2
0 1

예제 출력

2.0

예제 입력 2

2
0 0

예제 출력 2

1.5

예제 입력 3

3
0 1 1

예제 출력 3

2.5

예제 입력 4

4
0 1 1 2

예제 출력 4

3.166666666666667

힌트

첫 번째 예제의 경우에 모든 친구는 싫어하는 친구가 없다. 따라서, 순서에 상관없이 항상 두 명이 초대를 승낙한다.

두 번째 예제의 경우에 1번 친구는 0번 친구를 싫어한다. (0, 1) 순서로 초대할 때는 0은 승낙하고 1은 거절한다. (1, 0) 순서로 초대를 한다면, 1도 승낙하고 0도 승낙하게 된다.

세 번째 예제의 경우에 0과 1은 싫어하는 친구가 없고, 2는 친구 1을 싫어한다.

총 세 명의 친구가 있기 때문에, 가능한 순서는 6가지가 있다. 예를 들어, (1, 0, 2)의 순서로 친구를 초대한다면, 1과 0은 승낙하지만, 2는 거절을 하게 된다. (2, 1, 0) 순서로 초대를 한다면, 모든 친구가 초대를 승낙한다.

출처