← 返回题目列表

AtCoder · abc189_f

F. 双六2

中文机器翻译题面 查看原题

分数: 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