No.1857 Gacha Addiction

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

No.1857 Gacha Addiction

レベル : / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 32
作問者 :

Mitarushi / テスター :

蜜蜂

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 (\mod 998244353)$ かつ $0 \leq R < 998244353$ を満たす整数 $R$ が一意に定まることが証明できるので $R$ を出力してください。

入力

 $N$   $S$ 
 $P_{1} P_{2} \dots 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 (\mod 998244353)

より、

R = 499122179

となります。

サンプル2

入力

1 2021
2021

出力

確率 $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もしくは右上の雲マークをクリックしてアカウントを作成してください。

yukicoder

No.1857 Gacha Addiction

問題文

入力

出力

サンプル

サンプル1

入力

出力

サンプル2

入力

出力

サンプル3

入力

出力

サンプル4

入力

出力