No.3153 probability max K
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 98
作問者 :
Cafe1942
/ テスター :
kazuppa
sclara
タグ : / 解いたユーザー数 98
作問者 :


問題文最終更新日: 2025-05-29 17:54:22
問題文
$X$ 面ダイスとは、$X$ 面あり、$1$ から $X$ までの非負整数がすべて $1$ つずつ含まれているダイスである。また、どの面が出る確率も同様に確からしいものとする。
$N$ 個のダイスを振ります。 $i(1 \leq i \leq N)$ 番目のダイスは $A_i$ 面ダイスです。このとき、 $N$ 個の出目のうち最も大きい値がちょうど $K$ となる確率を有理数 $\text{mod} \ 998244353$ で求めてください。
有理数 $\text{mod} \ 998244353$ とは
その値を既約分数 $\frac{P}{Q}$ で表した時、 $Q \not \equiv 0 \pmod{998244353}$ であるような有理数に対して、 $R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353$ を満たす整数 $R$ が一意に定まり、 $\frac{P}{Q}$ をこの $R$ で表現します。制約
- $1 \leq N \leq 2 \times 10^{5}$
- $1 \leq K \leq 998244352$
- $1 \leq A_i \leq 998244352 (1 \leq i \leq N)$
- 入力はすべて整数
入力
$N$ $K$ $A_1$ $A_2$ $\dots$ $A_N$
出力
確率を有理数 $\text{mod} \ 998244353$ で出力してください。
サンプル
サンプル1
入力
2 5 6 6
出力
748683265
$6$ 面ダイスを $2$ 個振って、最大の出目がちょうど $5$ となる確率は $\frac{1}{4}$ です。
サンプル2
入力
1 1 1
出力
1
$1$ 面ダイスを $1$ 個振って最大の目がちょうど $1$ になる確率は $1$ です。
サンプル3
入力
7 7 7 2 11 13 5 3 17
出力
479675858
確率は $\frac{5}{77}$ です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。