https://www.acmicpc.net/problem/28139
문제 요약
- n개의 서로 다른 좌표가 주어짐
- n! 경우의 수.... 경로 이동 거리의 평균 구학
- n = 5000
접근법
- 모든 경우의 수를 구하지는 못함
- 특정 구간이 n! 경우의 수에서 몇 번 쓰일까?
- 특정 구간을 묶어 놓고 보면 (n - 1)! 경우의 수 발생
- 특정 구간은 서로 교차 가능
- 즉 특정 구간은 총 (n - 1)! * 2 번 쓰임
- 총 합은 (특정 구간들의 합) (n - 1)! 2
- 평균은 n!로 나눔
- (특정 구간들의 합) * 2 / n 을 구하면 되고, 특정 구간은 n^2이면 구함
newbieski