F - Sugoroku2

得分：600分

问题描述

高桥正在玩数格子游戏。

棋盘上有$N+1$个方格，编号从$0$到$N$。 高桥从方格$0$出发，前往方格$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$

输出

输出高桥赢得游戏之前旋转轮盘的次数的期望值。 当输出的绝对误差或相对误差与我们的答案之间最大为$10^{-4}$时，将其视为正确输出。 如果无法赢得游戏，请输出-1。

2 2 0

1.5000

如果在第一次旋转时轮盘显示$1$，他需要旋转两次才能赢得游戏；如果轮盘显示$2$，他只需要旋转一次就能赢得游戏。因此，旋转次数的期望值为$1.5$。

2 2 1
1

2.0000

如果轮盘显示$1$，他前进到方格$1$，但它将他送回方格$0$。

因此，他会继续旋转轮盘直到出现$2$并赢得游戏。

他第一次在第$i$次旋转时得到$2$的概率为$\frac{1}{2^i}$，因此旋转次数的期望值为$\sum_{i = 1}^{\infty} (i \times \frac{1}{2^i}) = 2$。

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

-1

100000 2 2
2997 92458

201932.2222