問題一覧 > 通常問題

No.3540 Arise

レベル : / AI推定難易度 : 2475 / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 11
作問者 : nauclhlt / テスター : MM gomaazarasi
お気に入りにしたユーザー ProblemId : 13163 / 自分の提出
問題文最終更新日: 2026-05-08 21:10:40
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 499 (順位表) の他の問題:

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$.

  1. Roll all $N$ dice.
  2. 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もしくは右上の雲マークをクリックしてアカウントを作成してください。