5607: Problem A. Accelerator
[Creator : ]
Description
DreamGrid is driving a spaceship from Mars to Earth.
There are $n$ accelerators on the trajectory to accelerate the spaceship. The $i$-th accelerator has an accelerating factor of $a_i$. The spaceship will pass the accelerators one by one. Initially, the velocity of the spaceship is $0$. When the spaceship passes through an accelerator, it gains energy from the accelerator and the velocity changes. Formally, if the accelerating factor is $A$ and the velocity before accelerating is $v$, the velocity after accelerating becomes $v^{\prime} = (v + 1) \times A$.
However, the $n$ accelerators are uniformly randomly shuffled. DreamGrid doesn’t know the order of the accelerators passed through now. Can you tell him the expected velocity after passing through all the $n$ accelerators?
It can be proved that the expected velocity is rational. Suppose that the answer can be denoted by $\frac{u}{d}$ where $gcd(u,\ d) = 1$, you need to output an integer $r$ such that $rd \equiv$ u\ (mod $998244353$) and $0 \leq r < 998244353$. It can be proved that such $r$ exists and is unique.
There are $n$ accelerators on the trajectory to accelerate the spaceship. The $i$-th accelerator has an accelerating factor of $a_i$. The spaceship will pass the accelerators one by one. Initially, the velocity of the spaceship is $0$. When the spaceship passes through an accelerator, it gains energy from the accelerator and the velocity changes. Formally, if the accelerating factor is $A$ and the velocity before accelerating is $v$, the velocity after accelerating becomes $v^{\prime} = (v + 1) \times A$.
However, the $n$ accelerators are uniformly randomly shuffled. DreamGrid doesn’t know the order of the accelerators passed through now. Can you tell him the expected velocity after passing through all the $n$ accelerators?
It can be proved that the expected velocity is rational. Suppose that the answer can be denoted by $\frac{u}{d}$ where $gcd(u,\ d) = 1$, you need to output an integer $r$ such that $rd \equiv$ u\ (mod $998244353$) and $0 \leq r < 998244353$. It can be proved that such $r$ exists and is unique.
Input
There are multiple test cases. The first line of the input contains an integer $T\ (1 \leq T < 100 000)$, indicating the number of test cases. For each test case:
The first line contains an integer $n\ (1 \leq n \leq 100 000)$, indicating the number of accelerators.
The next line contains n integers $a_1,\ a_2,\ \cdots ,\ a_n\ (1 \leq a_i \leq 10^9)$, indicating the accelerating factors.
It’s guaranteed that the sum of $n$ of all test cases will not exceed $100 000$.
The first line contains an integer $n\ (1 \leq n \leq 100 000)$, indicating the number of accelerators.
The next line contains n integers $a_1,\ a_2,\ \cdots ,\ a_n\ (1 \leq a_i \leq 10^9)$, indicating the accelerating factors.
It’s guaranteed that the sum of $n$ of all test cases will not exceed $100 000$.
Output
For each test case output one line containing the integer $r$.
Sample 1 Input
3
3
1 2 3
1
10
4
5 5 5 5
Sample 1 Output
665496247
10
780
there are $6$ ways to order the accelerators:
$[1,\ 2,\ 3]:\ v = ((((0 + 1) 1 + 1) 2) + 1) 3 = 15$
$[1,\ 3,\ 2]:\ v = ((((0 + 1) 1 + 1) 3) + 1) 2 = 14$
$[2,\ 1,\ 3]:\ v = ((((0 + 1) 2 + 1) 1) + 1) 3 = 12$
$[2,\ 3,\ 1]:\ v = ((((0 + 1) 2 + 1) 3) + 1) 1 = 10$
$[3,\ 1,\ 2]:\ v = ((((0 + 1) 3 + 1) 1) + 1) 2 = 10$
$[3,\ 2,\ 1]:\ v = ((((0 + 1) 3 + 1) 2) + 1) 1 = 9$
So the expected velocity is $\frac{15+14+12+10+10+9}{3!}=\frac{70}{6}$.
$[1,\ 2,\ 3]:\ v = ((((0 + 1) 1 + 1) 2) + 1) 3 = 15$
$[1,\ 3,\ 2]:\ v = ((((0 + 1) 1 + 1) 3) + 1) 2 = 14$
$[2,\ 1,\ 3]:\ v = ((((0 + 1) 2 + 1) 1) + 1) 3 = 12$
$[2,\ 3,\ 1]:\ v = ((((0 + 1) 2 + 1) 3) + 1) 1 = 10$
$[3,\ 1,\ 2]:\ v = ((((0 + 1) 3 + 1) 1) + 1) 2 = 10$
$[3,\ 2,\ 1]:\ v = ((((0 + 1) 3 + 1) 2) + 1) 1 = 9$
So the expected velocity is $\frac{15+14+12+10+10+9}{3!}=\frac{70}{6}$.