No.3540 Arise
タグ : / 解いたユーザー数 11
作問者 :
nauclhlt
/ テスター :
MM
Problem Statement
There are $N$ dice, numbered die $1, 2, \cdots, N$. Die $i$ shows each integer from $1$ to $A_i$ with equal probability.
Find the expected value of the sum of the values shown on the $N$ dice after performing the following $2$ actions in succession, $\mod 998244353$.
- Roll all $N$ dice.
- Let $x_i$ denote the value shown on die $i$ at the point after action $1$ has been performed. Let $\displaystyle S:=\argmin_{1\leq i\leq N} x_i$, and choose $k$ satisfying $\displaystyle k\in \argmax_{i\in S} A_i$ uniformly at random. Change the value shown on die $k$ to $A_k$.
What is the expected value $\mod{998244353}$?
The expected value to be found can be expressed in the form $\displaystyle \frac{Q}{P}$ using positive integers $P, Q$.
Then there exists a unique $R(1\leq R<998244353)$ satisfying $PR\equiv Q \pmod{998244353}$, so find this $R$.
Input
$N$ $A_1\ A_2\ \cdots\ A_N$
- $1\leq N\leq 2000$
- $1\leq A_i< 998244353$
- All inputs are integers.
Output
Print on one line the expected value of the sum of the values shown on the $N$ dice after performing the $2$ actions in succession, $\mod 998244353$.
End the output with a newline.
Subtasks
You receive partial points if you correctly solve a subtask satisfying the respective constraints.
- Subtask 1: (30%)
- $A_i\leq 2000$
- $A_1, A_2, \cdots, A_N$ are pairwise distinct. That is, $i\neq j\Rightarrow A_i\neq A_j$.
- Subtask 2: (70%)
- No additional constraints.
Sample
Sample 1
Input
2 1 2
Output
3
Let $x_i$ be the value shown on die $i$, and represent the state of the dice as $(x_1, x_2)$.
When the dice are rolled in action $1$, if the result is $(1, 1)$, die $2$ is chosen in action $2$, and the final state is $(1, 2)$. On the other hand, if the result is $(1, 2)$, die $1$ is chosen in action $2$, and the final state is $(1, 2)$.
In either case, the sum of the values after action $2$ is $3$, so print 3.
Sample 2
Input
10 3 1 4 5 9 2 6 8 7 10
Output
37
Sample 3
Input
12 878825912 909264886 901795690 930676853 836468367 831102254 819809798 964366341 810812837 848959043 881857880 922324655
Output
132037497
Of the $3$ samples, only this case does not satisfy the constraints of Subtask 1. That is, if you aim only for the partial points of Subtask 1, you do not need to answer this case correctly.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。