分数: 600 点
问题陈述
高桥正在玩双六。
主板有 N+1 编号的方块 0 to N。 高桥从 Square 开始 0 前往 Square N.
在这个双六中,我们使用轮盘显示来自 1 通过 M 具有相同的概率。 在每一回合中,高桥旋转轮盘并按照轮盘显示的数字前进。当他到达广场时 N 或者超越它,他赢了。
部分方块将他传送至方块 0 当他停在他们身上时。 有 K 这样的方块:正方形 A_1, \ldots, A_K.
求高桥获胜前转动轮盘的次数的期望值。
如果不可能获胜,请打印 -1 。
约束
- 输入中的所有值都是整数。
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 0 \leq K \leq 10
- 0 < A_1 < \ldots < A_K < N
输入
输入由标准输入按以下格式给出:
N M K A_1 \ldots A_K
输出
打印 Takahashi 在获胜之前旋转轮盘的次数的期望值。
当您的输出与我们答案的绝对或相对误差最多为 10^{-3}。
如果不可能获胜,请打印 -1 。
示例输入 1
2 2 0
示例输出 1
1.5000
如果车轮显示 1 在第一次旋转中,他需要旋转两次才能获胜;如果车轮显示 2 在第一轮中,他需要一次旋转才能获胜。因此,预期的自旋次数为 1.5.
示例输入 2
2 2 1 1
示例输出 2
2.0000
如果车轮显示 1,他前进到 Square 1,但这将他送回 Square 0.
因此,他不断旋转轮子,直到他得到 2 并获胜。
他得到的概率 2 首次在 i第旋转是 \frac{1}{2^i},所以预期的旋转次数是 \sum_{i = 1}^{\infty} (i \times \frac{1}{2^i}) = 2.
示例输入 3
100 6 10 11 12 13 14 15 16 17 18 19 20
示例输出 3
-1
示例输入 4
100000 2 2 2997 92458
示例输出 4
201932.2222