問題一覧 > 通常問題

No.1857 Gacha Addiction

レベル : / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 31
作問者 : MitarushiMitarushi / テスター : 蜜蜂蜜蜂
1 ProblemId : 6789 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-02-26 00:10:04

問題文

$N$ 個の品物が出るガチャガチャがあり、番号 $i$ の品物が出る確率は各試行で独立で、$\frac{P_i}{S}$ です。
このガチャガチャをいずれかの品物が被るまで引く操作を繰り返します。終了までに引いた回数の期待値を求めてください。

ここで、答えが互いに素である $2$ つの $0$ 以上の整数 $P,Q$ を用いて $\frac{P}{Q}$ と表現可能であることと、 $R \times Q \equiv P (\mathrm{mod}\ 998244353)$ かつ $0 \leq R < 998244353$ を満たす整数 $R$ が一意に定まることが証明できるので $R$ を出力してください。

入力

$N$ $S$
$P_1\ P_2\ \ldots\ P_N$

  • $1 \leq N \leq 1.5 \times 10^5$
  • $N \leq S < 998244353$
  • $1 \leq P_i\ (1 \leq i \leq N)$
  • $\sum_{i=1}^{N} P_i = S$
  • 入力はすべて整数

    • 出力

    問題に従って求めた $R$ を出力し、最後に改行してください。

    サンプル

    サンプル1
    入力
    2 2
    1 1
    出力
    499122179

    • 確率 $\frac{1}{4}$ で番号 $1$ の品物を $2$ 回連続で引きます。
    • 確率 $\frac{1}{4}$ で番号 $2$ の品物を $2$ 回連続で引きます。
    • 確率 $\frac{1}{8}$ で番号 $1,2,1$ の順で品物を $3$ 回引きます。
    • 確率 $\frac{1}{8}$ で番号 $1,2,2$ の順で品物を $3$ 回引きます。
    • 確率 $\frac{1}{8}$ で番号 $2,1,1$ の順で品物を $3$ 回引きます。
    • 確率 $\frac{1}{8}$ で番号 $2,1,2$ の順で品物を $3$ 回引きます。
    以上より答えは $\frac{5}{2}$ となります。 $499122179 \times 2 \equiv 5 (\mathrm{mod}\ 998244353)$ より、 $R=499122179$ となります。

    サンプル2
    入力
    1 2021
    2021
    出力
    2

    確率 $1$ で番号 $1$ の品物を $2$ 回連続で引くので、答えは $2$ となります。

    サンプル3
    入力
    5 14
    3 1 4 1 5
    出力
    418612855

    答えは $\frac{54041}{16807}$ です。

    サンプル4
    入力
    7 148
    20 22 2 12 2 13 77
    出力
    411047094

    $2022$ 年の $2$ 月 $12$ 日と $2$ 月 $13$ 日に行われる高校入試を経て灘校 $77$ 回生が入学します。
    中学からいる「在来」に対し、「新高」と呼ばれます。

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。