問題一覧 > 通常問題

No.3153 probability max K

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 98
作問者 : Cafe1942 / テスター : kazuppa sclara
ProblemId : 12268 / 出題時の順位表 / 自分の提出
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。