No.1670 Many Gacha
タグ : / 解いたユーザー数 24
作問者 :
chineristAC
/ テスター :
nok0
問題文
chinerist 君は $N$ 種類のフィギュアを集めています。
フィギュアはガチャを引くことで手に入れることができます。ガチャは全部で $M$ 種類存在し、 $i$ 番目のガチャを引くとフィギュア $j\ (1 \le j \le A_i)$ のうちいずれか $1$ つがそれぞれ等確率で手に入ります。
chinerist 君は $N$ 種類のフィギュアをそれぞれ $1$ つ以上手に入れるまで、ガチャを引く回数の期待値ができるだけ小さくなるようにガチャを引き続けます。
chinerist 君がガチャを引く回数の期待値を求め、$\bmod 998244353$ で出力してください。
より正確には、期待値はある互いに素な整数 $P,\ Q$ を用いて $\frac{P}{Q}$ と表せ、 $P \equiv Q\times R\ (\bmod 998244353)$ を満たす整数 $R\ (0 \le R < 998244353)$ がただ$1$ つ存在することがこの問題の制約下で証明できます。
よって $R$ を出力してください。
入力
$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$
- 与えられる入力はすべて整数
出力
答えを出力してください。
最後に改行してください。
サンプル
サンプル1
入力
2 2 1 2
出力
499122179
$1$ 回目は chinerist 君は $2$ 番目のガチャを引きます。
フィギュア $1$ が出た場合は $2$ 番目のガチャをフィギュア $2$ が出るまで引き続けます。
フィギュア $2$ が出た場合は $1$ 番目のガチャを引いてフィギュア $1$ を手に入れて集め終わります。
よって chinerist 君がガチャを引く回数の期待値は $\displaystyle \frac{1}{2} \times 2 + \frac{1}{2} \sum_{k=1}^{\infty} \left(\frac{1}{2} \right)^k (k+1) = \frac{5}{2}$ と計算できます。
サンプル2
入力
5 3 1 3 5
出力
349385533
ガチャを引く回数の期待値は $\frac{189}{20}$ です。
サンプル3
入力
2000 10 20 123 234 456 489 1029 1342 1567 1890 2000
出力
832309006
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。