시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB52201634.043%

문제

세준이는 가방을 하나 가지고 있다. 이 가방 속에는 N개의 공이 들어있다. N개의 공엔 색이 칠해져 있다. 세준이는 이 가방에서 서로 다른 두 개의 공을 하나씩 차례대로 고른다. 그 후에 두 번째로 고른 공을 첫 번째로 고른 공의 색으로 색 칠한다. 그 후, 공이 마르면, 두 공을 다시 가방에 집어 넣고 섞는다.

세준이는 이 공의 색이 모두 같아지려면 몇 번을 색 칠해야 하는지 궁금해졌다.

세준이가 공을 칠해야 하는 횟수의 기댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 공의 개수 N(1 ≤ N ≤ 24)이 주어진다. 둘째 줄에 공에 칠해진 N개의 색이 공백없이 주어진다. 색은 알파벳 대문자(A - Z)중 하나이다.

출력

첫째 줄에 세준이가 공을 색 칠하는 회수의 기댓값을 출력한다. 정답과의 절대/상대 오차는 10-8까지 허용한다.

예제 입력 1

3
ABA

예제 출력 1

3.0

예제 입력 2

2
AB

예제 출력 2

1.0

예제 입력 3

1
Q

예제 출력 3

0.0

예제 입력 4

7
AAAAAAA

예제 출력 4

0.0

예제 입력 5

3
KLM

예제 출력 5

4.0

예제 입력 6

5
AAABB

예제 출력 6

11.666666666666668

출처

  • 문제를 번역한 사람: baekjoon
  • 잘못된 번역을 찾은 사람: dotorya