| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 124 | 71 | 55 | 54.455% |
최근 P=NP 임을 증명하여 세계적인 스타가 된 김채완 교수는, 신학기에 그 증명을 리뷰하는 강의를 개설하였다. 이 강의는 김채완 교수의 훈훈한 외모에 힘입어 엄청난 인기를 얻었고, 결국 월향대의 모든 학생이 이 강의를 수강신청하기에 이르렀다.
자비로운 김채완 교수는 모든 학생에게 공평하게 기회를 주기 위해 각 학생이 뽑힐 확률이 균등하도록 정확히 $M$명을 뽑아 수강 자격을 주기로 하였다. 월향대학교에는 $N$개의 학부가 있고, $i$번째 학부에는 $A_i$명의 학생이 소속되어 있을 때, 수강 자격을 얻은 학생 중 학부가 같은 학생 쌍의 개수의 기댓값을 구해보자. 단, 한 학생은 정확히 하나의 학부에 소속되어 있다.
첫째 줄에 정수 $N,ドル $M$이 공백으로 구분되어 주어진다. $(1 \le N \le 500,000円;$ 1ドル \le M \le \sum A_i)$
둘째 줄에 각 학부에 소속된 학생의 수 $A_1,ドル $A_2,ドル $\cdots,ドル $A_N$이 공백으로 구분되어 정수로 주어진다. $(1 \le A_i;$ $\sum A_i \lt 998,244円,353円)$
수강 자격을 얻은 학생 중 학부가 같은 학생 쌍의 개수의 기댓값이 기약분수 $\frac{p}{q}$일 때, $p \equiv qr \pmod {998,244円,353円}$을 만족하는 0ドル$ 이상 998ドル,244円,353円$ 미만의 정수 $r$을 출력한다. 기댓값은 항상 유리수이며, $r$은 유일하다.
1 2 3
1
모든 학생이 같은 학부에 속해 있으므로 어떤 2ドル$명의 학생을 고르더라도 같은 학부에 속한 학생은 1ドル$쌍이다. 따라서 구하는 기댓값은 $\frac{1}{1}$이다. 1ドル \equiv 1 \times r \pmod {998,244円,353円}$을 만족하는 $r$은 1ドル$이므로, 1을 출력한다.
3 2 1 2 3
465847365
구하는 기댓값은 $\frac{4}{15}$이다. 4ドル \equiv 15 \times r \pmod {998,244円,353円}$을 만족하는 $r$은 465ドル,847円,365円$이므로, 465847365를 출력한다.
Contest > BOJ User Contest > 월간 향유회 > 월간 향유회 2023. 10. E번