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

输入 #1

2 2 0

输出 #1

1.5000

输入输出样例 #2

输入 #2

2 2 1
1

输出 #2

2.0000

输入输出样例 #3

输入 #3

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

输出 #3

-1

输入输出样例 #4

输入 #4

100000 2 2
2997 92458

输出 #4

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

第一次轮盘若转到 $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 翻译