시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 512 MB | 67 | 53 | 45 | 83.333% |
농부 존에게는 N마리의 소가 있다. 소들의 키는 다양하며, 두 마리의 소의 키가 서로 같을 수 있다.
자신의 헤어스타일이 마음에 들지 않았던 소들은 일렬로 서서 서로의 헤어스타일을 확인해 주려고 한다.
각 소들은 자신의 오른쪽을 바라보면서 자신보다 키가 같거나 큰 소가 등장하기 전까지 나온 모든 소들의 헤어스타일을 확인할 수 있다. 더 정확하게는, 왼쪽에서 i번째에 서 있는 소의 키를 H'i라 하면, i번째 소는 다음 조건을 만족할 때 (또한 그러할 때에만) j번째 소를 볼 수 있다.
소들이 N마리 있으므로, 그들이 일렬로 설 수 있는 방법은 총 N!가지다. 농부 존은 헤어스타일을 확인할 수 있는 소들 쌍의 수의 기댓값이 궁금해졌다. 농부 존을 도와, 이 기댓값을 출력하는 프로그램을 작성하시오.
첫 번째 줄에 소의 수를 나타내는 자연수 N이 주어진다.
두번째 줄에 N마리의 소의 키를 나타내는 N개의 자연수 H1, ···, HN가 사이에 공백을 두고 주어진다.
어떤 서로소이고 음이 아닌 두 정수 $P$, $Q$가 존재하여, 헤어스타일을 확인할 수 있는 소들 쌍의 수의 기댓값이 $\displaystyle \frac{P}{Q}$와 같다고 하자. 이때, $P \equiv QX \pmod{10^{9} + 7}$를 만족하는 0 이상 (109 + 7) 미만의 정수 $X$를 구하여 첫 번째 줄에 출력한다.
조건을 만족하는 $P$, $Q$, $X$는 반드시 존재한다. 또한 $X$는 유일하게 존재함이 보장된다.
모든 입력 데이터는 다음 조건을 만족한다.
4 1 1 2 2
333333337
첫번째 입출력 예제에서, 소들이 일렬로 설 수 있는 방법과 헤어스타일을 확인할 수 있는 소들 쌍의 수는 아래 표와 같다.
소들이 일렬로 선 방법 | 헤어스타일을 확인할 수 있는 소 쌍의 수 |
1, 1, 2, 2 | 0 |
1, 2, 1, 2 | 1 |
1, 2, 2, 1 | 1 |
2, 1, 1, 2 | 2 |
2, 1, 2, 1 | 2 |
2, 2, 1, 1 | 2 |
따라서 기댓값은 $\displaystyle \frac{0 + 1 + 1 + 2 + 2 + 2}{6} = \frac{4}{3}$다.
4 10 20 30 40
416666672
High School > 경기과학고등학교 > 나는코더다 2019 송년대회 J번