No.3540 Arise
タグ : / 解いたユーザー数 10
作問者 :
nauclhlt
/ テスター :
MM
gomaazarasi
問題文
サイコロ $1, 2, \cdots, N$ までの $N$ 個のサイコロがあり、サイコロ $i$ は $1$ から $A_i$ までの整数が等確率に出るサイコロです。
次の $2$ つの行動を続けて行った後の $N$ 個のサイコロの出目の総和の期待値を $\mod 998244353$ で求めてください。
- $N$ 個のサイコロをすべて振る
- 行動 $1$ を行った後の時点でのサイコロ $i$ の出目を $x_i$ で表す。$\displaystyle S:=\argmin_{1\leq i\leq N} x_i$ として, $\displaystyle k\in \argmax_{i\in S} A_i$ を満たす $k$ を一様ランダムに選ぶ。サイコロ $k$ の出目を $A_k$ に変更する
期待値 $\mod{998244353}$ とは
求める期待値は正整数 $P, Q$ を用いて $\displaystyle \frac{Q}{P}$ の形に表せます。
このとき、$PR\equiv Q \pmod{998244353}$ を満たす $R(1\leq R<998244353)$ が一意に存在するので、この $R$ を求めてください。
入力
$N$ $A_1\ A_2\ \cdots\ A_N$
- $1\leq N\leq 2000$
- $1\leq A_i< 998244353$
- 入力はすべて整数
出力
$2$ つの行動を続けて行った後の $N$ 個のサイコロの出目の総和の期待値 $\mod 998244353$ を一行に出力してください。
最後に改行してください。
部分点
各制約を満たすサブタスクに正解した場合、部分点が与えられます。
- サブタスク1: (30%)
- $A_i\leq 2000$
- $A_1, A_2, \cdots, A_N$ は互いに相異なる。すなわち $i\neq j\Rightarrow A_i\neq A_j$
- サブタスク2: (70%)
- 追加の制約はない
サンプル
サンプル1
入力
2 1 2
出力
3
サイコロ $i$ の出目を $x_i$ として $(x_1, x_2)$ のように出目の状況を表します。
行動 $1$ でサイコロを振ったとき、$(1, 1)$ であれば行動 $2$ で サイコロ $2$ が選ばれ、最終的には $(1, 2)$ となります。一方で $(1, 2)$ であれば、行動 $2$ でサイコロ $1$ が選ばれ、最終的には $(1, 2)$ となります。
いずれにせよ、行動 $2$ が終わった後の出目の総和は $3$ となるため、3 を出力します。
サンプル2
入力
10 3 1 4 5 9 2 6 8 7 10
出力
37
サンプル3
入力
12 878825912 909264886 901795690 930676853 836468367 831102254 819809798 964366341 810812837 848959043 881857880 922324655
出力
132037497
$3$ つのサンプルのうちこのケースのみサブタスク1の制約を満たしません。すなわち、サブタスク1の部分点のみを得る場合、このケースに正答する必要はありません。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。