No.1670 Many Gacha
タグ : / 解いたユーザー数 27
作問者 :
chineristAC
/ テスター :
nok0
Problem Statement
chinerist is collecting $N$ types of figures.
Figures can be obtained by pulling gachas. There are $M$ types of gacha in total, and pulling the $i$-th gacha gives $1$ of the figures $j\ (1 \le j \le A_i)$, each with equal probability.
chinerist keeps pulling gachas until he has obtained at least $1$ of each of the $N$ types of figures, pulling in such a way that the expected number of pulls is as small as possible.
Find the expected number of pulls chinerist makes, and output it $\bmod 998244353$.
More precisely, the expected value can be expressed as $\frac{P}{Q}$ using some coprime integers $P,\ Q$, and it can be proved under the constraints of this problem that there exists exactly $1$ integer $R\ (0 \le R < 998244353)$ satisfying $P \equiv Q\times R\ (\bmod 998244353)$.
Therefore, output $R$.
Input
$N$ $M$ $A_1$ $A_2$ $\dots$ $A_M$
- $1\le N \le 2 \times 10^5$
- $1\le M \le N$
- $1 \le A_i \le N\ (1\le i \le M)$
- $A_i < A_{i+1}\ (1\le i \le M-1)$
- $A_M=N$
- All input values are integers.
Output
Output the answer.
Print a newline at the end.
Sample
Sample 1
Input
2 2 1 2
Output
499122179
On pull number $1$, chinerist pulls the $2$-nd gacha.
If figure $1$ comes out, he keeps pulling the $2$-nd gacha until figure $2$ comes out.
If figure $2$ comes out, he pulls the $1$-st gacha, obtains figure $1$, and finishes collecting.
Therefore, the expected number of pulls chinerist makes can be calculated as $\displaystyle \frac{1}{2} \times 2 + \frac{1}{2} \sum_{k=1}^{\infty} \left(\frac{1}{2} \right)^k (k+1) = \frac{5}{2}$.
Sample 2
Input
5 3 1 3 5
Output
349385533
The expected number of pulls is $\frac{189}{20}$.
Sample 3
Input
2000 10 20 123 234 456 489 1029 1342 1567 1890 2000
Output
832309006
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。