Sugoroku2

题目描述

Takahashi 在玩双陆棋（sugoroku）。 棋盘有 $N+1$ 个格子，编号为 $0$ 到 $N$。 Takahashi 从格子 $0$ 出发，目标是到达格子 $N$。 在这个双陆棋中，我们使用一个指示 $1$ 到 $M$ 的轮盘，每个数字出现的概率相等。 每一回合，Takahashi 旋转轮盘并前进轮盘显示的步数。当这使他到达格子 $N$ 或超过它时，他就获胜。 有些格子会在他停在上面时把他送回格子 $0$。 这样的格子有 $K$ 个：格子 $A_1, \ldots, A_K$。 求 Takahashi 在获胜前旋转轮盘的期望次数。 如果不可能获胜，输出 $-1$。

输入格式

输入从标准输入给出，格式如下： $N$ $M$ $K$ $A_1$ $\ldots$ $A_K$

输出格式

输出 Takahashi 在获胜前旋转轮盘的期望次数。 当你的输出与我们的答案的绝对或相对误差至多 $10^{-3}$ 时，将视为正确。 如果不可能获胜，输出 $-1$。

2 2 0

1.5000

2 2 1
1

2.0000

100 6 10
11 12 13 14 15 16 17 18 19 20

-1

100000 2 2
2997 92458

201932.2222

提示

所有输入值均为整数。 $1 \leq N \leq 10^5$ $1 \leq M \leq 10^5$ $0 \leq K \leq 10$ 0 < A_1 < \ldots < A_K < N如果轮盘在第一回合显示 $1$，他将需要两次旋转才能获胜；如果轮盘在第一回合显示 $2$，他将需要一次旋转获胜。因此，期望旋转次数为 $1.5$。
如果轮盘显示 $1$，他前进到格子 $1$，但它会把他送回格子 $0$。
因此，他会不断旋转轮盘直到得到 $2$ 并获胜。
在第 $i$ 次旋转时第一次得到 $2$ 的概率是 $\frac{1}{2^i}$，所以期望旋转次数为 $\sum_{i = 1}^{\infty} (i \times \frac{1}{2^i}) = 2$。

标签: AtCoder|abc189F

来源

AtCoder|abc189F