28299번 - 반전수

$a_1$개의 $1$, $a_2$개의 2, $\dots$, $a_n$개의 $n$으로 이루어진 수열들을 생각하자. 해당 수들로 이루어진 수열 중에 한 개를 균일한 확률로 무작위로 고를 때 반전수의 제곱의 기댓값을 $998\, 244\, 353$으로 나눈 나머지를 구하여라.

수열 $p_1$, $p_2$, $\dots$, $p_n$의 반전수는 $i<j$, $p_i>p_j$를 만족하는 순서쌍 $(i,j)$의 개수로 정의한다.

첫 번째 줄에 수열에 있는 수의 최댓값 $n$이 주어진다. ($2\leq n\leq 200\, 000$)

두 번째 줄에 각 수의 개수 $a_i$가 공백을 사이에 두고 주어진다. ($1\leq a_i$; $n\leq\sum_{i=1}^{n}a_i\leq 998\, 244\, 352$).

문제에서 요구하는 정답을 $998\, 244\, 353$으로 나눈 나머지를 출력하여라.

반전수의 제곱의 기댓값이 유리수임을 증명할 수 있다. 이 수를 $\frac{p}{q}$ ($p$, $q$는 서로소)로 표시했을 때, $q$는 $998\, 244\, 353$의 배수가 될 수 없음을 증명할 수 있다. $aq\equiv p\ (\mathrm{mod}\ 998\, 244\, 353)$을 만족하는 음이 아닌 정수 $a$ 중 가장 작은 수를 $\frac{p}{q}$를 $998\, 244\, 353$으로 나눈 나머지로 정의한다.

$1$이 $1$개, $2$가 $1$개로 이루어진 수열은 $12$, $21$ 두 가지가 있고 각 수열의 반전수는 $0$, $1$이다. 즉, 반전수의 제곱의 기댓값은 $\frac{1}{2}$가 되고 $499\, 122\, 177\times 2\equiv 1\ (\mathrm{mod}\ 998\, 244\, 353)$이기 때문에 $499\, 122\, 177$이 정답이 된다.