No.1857 Gacha Addiction
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$
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.
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
蜜蜂