Josh’s Double Bacon Deluxe
시간 제한2초메모리 제한512 MB
줄을 선 사람들이 원하는 버거가 남아 있으면 그것을, 없으면 남은 것 중 하나를 무작위로 가져갈 때 마지막 사람이 원하는 버거를 받을 확률을 구한다.
문제
On their way to the contest grounds, Josh, his coach, and his N − 2 teammates decide to stop at a burger joint that offers M distinct burger menu items. After ordering their favourite burgers, the team members line up, with the coach in the first position and Josh last, to pick up their burgers. Unfortunately, the coach forgot what he ordered. He picks a burger at random and walks away. The other team members, in sequence, pick up their favourite burger if available, or a random remaining burger if there are no more of their favourite burger. What is the probability that Josh, being last in line, will get to eat his favourite burger?
입력
The first line contains the number N (3 ≤ N ≤ 1 000 000), the total number of people and burgers. The next line contains N numbers, the i-th being bi (1 ≤ bi ≤ M ≤ 500 000), denoting the item number of the i-th person’s favourite burger. The first person in line is the coach, and the N-th person is Josh.
출력
Output a single number P, the probability that Josh will get to eat his favourite burger, bN. If the correct answer is C, the grader will view P correct if |P − C| < 10−6.