시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 1024 MB59303060.000%

문제

국가원수로서, 당신은 시우 제국에 닥칠 폭우를 대비해야 한다. 시우 제국에는 $N$개의 도시가 있으며, $i$번 도시는 제방과 수도시설의 개발 수준에 따른 피해 가중치 $A_i$를 가진다. 모든 도시에는 비가 올 예정이며, 도시별로 강수량을 $0$ 이상 $1$ 이하 범위의 실수로 표현할 것이다. 유감스럽게도 예보 시스템의 한계로 인하여 각 도시의 정확한 강수량은 알 수 없었다. 따라서, 당신은 강수량이 도시마다 독립적이고 앞서 말한 범위 내에서 균등분포를 따를 것이라고 가정하기로 했다. 도시는 강수량에 피해 가중치를 곱한 만큼의 피해를 입는다. 이를테면 $1$번 도시의 강수량과 피해 가중치가 각각 $0.5$, $3$일 경우, $1$번 도시는 $1.5$만큼의 피해를 받게 될 것이다.

당신은 대비책을 세우기에 앞서 각 도시가 $N$개의 도시 중 가장 큰 피해를 받은 도시가 될 확률을 구해두려고 한다. 가령 $2$개의 도시가 있어 각각의 피해 가중치가 $1$, $2$라면, $1$번 도시가 $0.25$, $2$번 도시는 $0.75$가 된다. $N$개의 도시의 피해 가중치가 입력으로 주어질 때, 각 도시가 가장 큰 피해를 받은 도시가 될 확률을 출력하라.

입력

첫 번째 줄에 $N$이 주어진다. ($1 \le N \le 10^6$)

두 번째 줄에 각 도시의 피해 가중치 $A$의 값이 순서대로 주어진다. ($0 < A_i < 998\,244\,353$)

입력으로 주어지는 수는 모두 정수이다.

출력

$N$개의 줄에 걸쳐, $i$번째 줄에 $i$번째 도시가 가장 큰 피해를 받은 도시가 될 확률을 $998\,244\,353$으로 나눈 나머지를 출력한다. 정확히 말하면, 정답을 적당한 자연수 $x$, $y$가 있어 $\frac{x}{y}$로 표현 가능할 때 $x \equiv yz \pmod{998\,244\,353}$를 만족하는 $0$ 이상 $998\,244\,353$ 미만의 정수 $z$를 출력한다.

예제 입력 1

2
1 2

예제 출력 1

748683265
249561089

$1$번 도시가 가장 큰 피해를 받은 도시가 될 확률은 $0.25$이다. $0.25 = \frac{1}{4}$이므로, $1 \equiv 4 \times z \pmod{998\,244\,353}$를 만족하는 값인 $748\,683\,265$를 출력한다.

$2$번 도시가 가장 큰 피해를 받은 도시가 될 확률은 $0.75$이다. $0.75 = \frac{3}{4}$이므로, $3 \equiv 4 \times z \pmod{998\,244\,353}$를 만족하는 값인 $249\,561\,089$를 출력한다.

출처

University > 서울사이버대학교 > 2025 서울사이버대학교 프로그래밍 경진대회 (SCUPC) I번