問題一覧 > 通常問題

No.1857 Gacha Addiction

レベル : / AI推定難易度 : 2200 / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 36
作問者 : Mitarushi / テスター : 蜜蜂
お気に入りにしたユーザー ProblemId : 6789 / 自分の提出
問題文最終更新日: 2022-02-26 00:10:04
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 333 (灘高入試コンテスト2022) (順位表) の他の問題:

Problem Statement

There is a gacha machine that dispenses $N$ kinds of items. In each draw, independently, the item numbered $i$ comes out with probability $\frac{P_i}{S}$.
You repeatedly draw from this gacha machine until some item is duplicated. Find the expected number of draws made until the process ends.

Here, it can be proved that the answer can be expressed as $\frac{P}{Q}$ using $2$ coprime integers $P,Q$ that are at least $0$, and that an integer $R$ satisfying $R \times Q \equiv P (\mathrm{mod}\ 998244353)$ and $0 \leq R < 998244353$ is uniquely determined. Output this $R$.

Input

$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$
  • All input values are integers.
  • Output

    Output $R$ as determined by the problem statement, followed by a newline.

    Sample

    Sample 1
    Input
    2 2
    1 1
    Output
    499122179

    • With probability $\frac{1}{4}$, you draw the item numbered $1$ $2$ times in a row.
    • With probability $\frac{1}{4}$, you draw the item numbered $2$ $2$ times in a row.
    • With probability $\frac{1}{8}$, you make $3$ draws, getting items numbered $1,2,1$ in this order.
    • With probability $\frac{1}{8}$, you make $3$ draws, getting items numbered $1,2,2$ in this order.
    • With probability $\frac{1}{8}$, you make $3$ draws, getting items numbered $2,1,1$ in this order.
    • With probability $\frac{1}{8}$, you make $3$ draws, getting items numbered $2,1,2$ in this order.
    From the above, the answer is $\frac{5}{2}$. Since $499122179 \times 2 \equiv 5 (\mathrm{mod}\ 998244353)$, we have $R=499122179$.

    Sample 2
    Input
    1 2021
    2021
    Output
    2

    With probability $1$, you draw the item numbered $1$ $2$ times in a row, so the answer is $2$.

    Sample 3
    Input
    5 14
    3 1 4 1 5
    Output
    418612855

    The answer is $\frac{54041}{16807}$.

    Sample 4
    Input
    7 148
    20 22 2 12 2 13 77
    Output
    411047094

    After the high school entrance exams held on $2$/$12$ and $2$/$13$ of the year $2022$, the $77$th class of Nada School will enroll.
    In contrast to the "Zairai" students, who have been there since junior high school, they are called "Shinko".

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