P1033 - Double Chance

Memory Limit：1024 MB Time Limit：2.000 S

Judge Style：Text Compare Creator：

Submit：15 Solved：6

Submit Submit Record Statistics ShowOff!

There are $lns="http://www.w3.org/1998/Math/MathML"> �$ cards called card $lns="http://www.w3.org/1998/Math/MathML"> 1$ , card $lns="http://www.w3.org/1998/Math/MathML"> 2$ , $lns="http://www.w3.org/1998/Math/MathML"> \dots$ , card $lns="http://www.w3.org/1998/Math/MathML"> �$ . On card $lns="http://www.w3.org/1998/Math/MathML"> �$ $lns="http://www.w3.org/1998/Math/MathML"> (1 \leq � \leq �)$ , an integer $lns="http://www.w3.org/1998/Math/MathML"> �_{�}$ is written.

For $lns="http://www.w3.org/1998/Math/MathML"> � = 1, 2, \dots, �$ , solve the following problem.

We have a bag that contains $lns="http://www.w3.org/1998/Math/MathML"> �$ cards: card $lns="http://www.w3.org/1998/Math/MathML"> 1$ , card $lns="http://www.w3.org/1998/Math/MathML"> 2$ , $lns="http://www.w3.org/1998/Math/MathML"> \dots$ , card $lns="http://www.w3.org/1998/Math/MathML"> �$ .
Let us perform the following operation twice, and let $lns="http://www.w3.org/1998/Math/MathML"> �$ and $lns="http://www.w3.org/1998/Math/MathML"> �$ be the numbers recorded, in the recorded order.

Draw a card from the bag uniformly at random, and record the number written on that card. Then, return the card to the bag.

Print the expected value of $lns="http://www.w3.org/1998/Math/MathML"> \max (�, �)$ , modulo $lns="http://www.w3.org/1998/Math/MathML"> 998244353$ (see Notes).
Here, $lns="http://www.w3.org/1998/Math/MathML"> \max (�, �)$ denotes the value of the greater of $lns="http://www.w3.org/1998/Math/MathML"> �$ and $lns="http://www.w3.org/1998/Math/MathML"> �$ (or $lns="http://www.w3.org/1998/Math/MathML"> �$ if they are equal).

The input is given from Standard Input in the following format:

$N$

 $A_{1}$   $lns="http://www.w3.org/1998/Math/MathML"> �_{2}$   $lns="http://www.w3.org/1998/Math/MathML"> \dots$   $lns="http://www.w3.org/1998/Math/MathML"> �_{�}$

$1 \leq N \leq 2 \times 1 0^{5}$
$lns="http://www.w3.org/1998/Math/MathML"> 1 \leq �_{�} \leq 2 \times 1 0^{5}$
All values in the input are integers.

Print $lns="http://www.w3.org/1998/Math/MathML"> �$ lines. The $lns="http://www.w3.org/1998/Math/MathML"> �$ -th line $lns="http://www.w3.org/1998/Math/MathML"> (1 \leq � \leq �)$ should contain the answer to the problem for $lns="http://www.w3.org/1998/Math/MathML"> � = �$ .

3
5 7 5

5
499122183
443664163

For instance, the answer for $lns="http://www.w3.org/1998/Math/MathML"> � = 2$ is found as follows.

The bag contains card $lns="http://www.w3.org/1998/Math/MathML"> 1$ and card $lns="http://www.w3.org/1998/Math/MathML"> 2$ , with $lns="http://www.w3.org/1998/Math/MathML"> �_{1} = 5$ and $lns="http://www.w3.org/1998/Math/MathML"> �_{2} = 7$ written on them, respectively.

If you draw card $lns="http://www.w3.org/1998/Math/MathML"> 1$ in the first draw and card $lns="http://www.w3.org/1998/Math/MathML"> 1$ again in the second draw, we have $lns="http://www.w3.org/1998/Math/MathML"> � = � = 5$ , so $lns="http://www.w3.org/1998/Math/MathML"> \max (�, �) = 5$ .
If you draw card $lns="http://www.w3.org/1998/Math/MathML"> 1$ in the first draw and card $lns="http://www.w3.org/1998/Math/MathML"> 2$ in the second draw, we have $lns="http://www.w3.org/1998/Math/MathML"> � = 5$ and $lns="http://www.w3.org/1998/Math/MathML"> � = 7$ , so $lns="http://www.w3.org/1998/Math/MathML"> \max (�, �) = 7$ .
If you draw card $lns="http://www.w3.org/1998/Math/MathML"> 2$ in the first draw and card $lns="http://www.w3.org/1998/Math/MathML"> 1$ in the second draw, we have $lns="http://www.w3.org/1998/Math/MathML"> � = 7$ and $lns="http://www.w3.org/1998/Math/MathML"> � = 5$ , so $lns="http://www.w3.org/1998/Math/MathML"> \max (�, �) = 7$ .
If you draw card $lns="http://www.w3.org/1998/Math/MathML"> 2$ in the first draw and card $lns="http://www.w3.org/1998/Math/MathML"> 2$ again in the second draw, we have $lns="http://www.w3.org/1998/Math/MathML"> � = � = 7$ , so $lns="http://www.w3.org/1998/Math/MathML"> \max (�, �) = 7$ .

These events happen with the same probability, so the sought expected value is $lns="http://www.w3.org/1998/Math/MathML"> \frac{5 + 7 + 7 + 7}{4} = \frac{13}{2}$ . We have $lns="http://www.w3.org/1998/Math/MathML"> 499122183 \times 2 \equiv 13 (m o d 998244353)$ , so $lns="http://www.w3.org/1998/Math/MathML"> 499122183$ should be printed.

Atcoder

Submit Submit Record Statistics ShowOff!

1033: Double Chance

Description

Input

Output

Sample Input Copy

Sample Output Copy

HINT

Source/Category