확률론 - 5000!개의 거리의 합의 평균을 구하는 방법

1. 문제 28139번: 평균 구하기 (acmicpc.net) 28139번: 평균 구하기 $2$차원 좌표평면 위에 $N$명의 사람이 있다. 위치가 ($x_1, y_1$)인 사람과 위치가 ($x_2, y_2$)인 사람 간의 거리는 $\sqrt{\left(x_1 - x_2 \right)^2 + \left(y_1 - y_2 \right)^ 2}$이다. 위대한 마법사 레이는 이 중 한 www.acmicpc.net 2. 풀이 최악의 경우 5000!가지를 모두 거리를 계산해봐서 평균을 구해야하는데, 당연히 2.5초안에 가능할리는 없고 5000!가지를 안구해봐도 구하는 방법이 있겠지 확률변수 $X$를 $N!$가지 각각 경우의 수에서 나올 수 있는 이동거리라고 정의하자. 문제에도 나와있듯이 "총이동거리는 해당 순서에서..