공 색칠하기의 기대값
시간 제한2초메모리 제한128 MB
N개의 색깔 구슬이 주어질 때, 모든 구슬이 같은 색이 될 때까지 필요한 무작위 재도색 연산의 기댓값을 구하는 문제입니다.
문제
세준이는 색이 칠해진 공 N개가 들어 있는 가방을 가지고 있다. 한 번의 작업은 다음과 같이 진행된다. 먼저 가방에서 공 하나를 고르고, 이어서 그 공과 다른 공 하나를 고른다. 두 번째로 고른 공은 첫 번째로 고른 공과 같은 색으로 다시 칠한다. 칠한 공이 마르면 두 공을 모두 가방에 다시 넣고 섞는다.
모든 공의 색이 같아질 때까지 필요한 색칠 작업 횟수의 기댓값을 구하시오.
입력
첫째 줄에 공의 개수 N이 주어진다. (1 ≤ N ≤ 24)
둘째 줄에는 각 공의 색을 나타내는 길이 N의 문자열이 주어진다. 문자열은 공백 없이 주어지며, 각 문자는 알파벳 대문자 A부터 Z 중 하나이다.
출력
모든 공의 색이 같아질 때까지 세준이가 공을 다시 칠하는 횟수의 기댓값을 출력한다.
정답과의 절대 오차 또는 상대 오차가 10^-8 이하이면 정답으로 인정된다.