버스 정류장
시간 제한2초메모리 제한512 MB
n개 노선의 대기 시간이 각각 [0, di]에서 독립적으로 균등 분포할 때 최솟값의 기댓값을 구해 998244353으로 나눈 나머지로 출력한다.
문제
버스 정류장에서 버스를 기다리고 있다.
정류장을 지나는 버스 노선이 n개 있다. i번 노선의 버스는 정확히 di분 간격으로 한 대씩 도착한다는 것을 알고 있다. 그러나 어느 노선이든 다음 버스가 정확히 언제 도착하는지는 알지 못하므로, i번 노선의 버스가 도착할 때까지의 시간은 0분과 di분 사이에서 균등하게 분포하는 실수라고 기대한다.
아무 노선의 버스든 도착할 때까지 걸리는 시간의 기댓값을 구하시오.
입력
첫째 줄에 노선의 수를 나타내는 정수 n (1 ≤ n ≤ 105)이 주어진다.
둘째 줄에 n개의 정수 d1, d2, . . . , dn (1 ≤ di ≤ 987 654 321)이 공백으로 구분되어 주어진다. di는 i번 노선 버스 사이의 간격(분)이다.
출력
답은 기약분수 P/Q로 나타낼 수 있다. 여기서 P와 Q는 서로소인 양의 정수이고 Q ≠ 0 (mod 998 244 353)이다. X = P·Q−1 (mod 998 244 353)를 출력하시오 (0 ≤ X < 998 244 353). Q−1은 998 244 353을 법으로 하는 Q의 역원이다.
힌트
첫 번째와 두 번째 예제의 답은 각각 3/2와 275/168이다.