AT_abc189_f [ABC189F] Sugoroku2

高桥君正在玩双六游戏。 这个双六游戏有 $N+1$ 个格子，编号从 $0$ 到 $N$。高桥君从 $0$ 号格子出发，目标是到达 $N$ 号格子。 在这个游戏中，有一个等概率出现 $1$ 到 $M$ 的 $M$ 种结果的轮盘。每一回合，高桥君旋转轮盘，并根据结果前进相应的步数。如果因此到达或越过 $N$ 号格子，则游戏结束。 此外，有一些格子是“返回起点”格子，停在这些格子上会被送回 $0$ 号格子。这些格子共有 $K$ 个，分别是 $A_1,\ldots,A_K$ 号格子。 请输出高桥君到达终点前，轮盘旋转的期望次数。如果无法到达终点，请输出 `-1`。

输入通过标准输入按以下格式给出。 > $N$ $M$ $K$ $A_1$ $...$ $A_K$

请输出高桥君到达终点前轮盘旋转的期望次数。若与标准答案的绝对误差或相对误差不超过 $10^{-3}$，则视为正确答案。如果无法到达终点，请输出 `-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$ ### 样例解释 1 第一次轮盘若转到 $1$，则需要 $2$ 次，若转到 $2$，则 $1$ 次即可到达终点，因此期望次数为 $1.5$。 ### 样例解释 2 轮盘转到 $1$ 时会到达 $1$ 号格子，但该格子为“返回起点”，所以会被送回 $0$ 号格子。因此需要不断旋转轮盘直到第一次转到 $2$，此时即可到达终点。第 $i$ 次首次转到 $2$ 的概率为 $\frac{1}{2^i}$，所以期望次数为 $\sum_{i=1}^{\infty} (i \times \frac{1}{2^i}) = 2$。 由 ChatGPT 4.1 翻译