P6633 [ZJOI2020] 抽卡

Bob 喜欢抽卡。 Bob 最近入坑了一款叫 “主公连结” 的抽卡游戏。游戏中共有 $n$ 个不同的角色，编号为 $1 \sim n$。当 Bob 获得其中的编号连续的 $k$ 张卡时，就可以组出理论最强阵容。 当期卡池中共有 $m$ 张不同的卡，每次抽卡，Bob 都可以等概率随机获得一张卡池中的卡。如果 Bob 抽到了一张他已经拥有的卡，那么什么事都不会发生，等于 Bob 浪费了这次抽卡机会。Bob 是个谨慎的人，他想知道，如果他不停地抽卡直到抽到编号连续的 $k$ 张卡时停止抽卡，期望需要抽多少轮。

无

无

**样例解释 1** 如果第一轮抽到的是 $2$ 号卡，那么期望需要抽 $1 + \frac{3}{2}$ 轮；如果第一轮抽到的是 $1$ 号卡或 $3$ 号卡，那么期望需要抽 $1 + 3$ 轮。故答案为 $\frac{1}{3}(1 + \frac{3}{2}) + \frac{2}{3}(1 + 3) = 3.5$ **数据范围与约定** 对于前 $10\%$ 的数据，$m \le 10$。 对于另外 $10\%$ 的数据，$m \le 500$ 且 $k = m−1$。 对于另外 $10\%$ 的数据，$m \le 500$ 且保证有且仅有一组理论最强阵容。 对于另外 $10\%$ 的数据，$m \le 500$ 且保证任意两组可抽出的理论最强阵容不交。 对于前 $50\%$ 的数据，$m \le 500$。 对于前 $70\%$ 的数据，$m \le 5000$。 对于另外 $10\%$ 的数据，$k = 5$。 对于另外 $10\%$ 的数据，$k = 2000$。 对于 $100\%$ 的数据，$1 \le m \le 200000,1 \le a_i \le 2m,2 \le k \le m$，保证卡池中至少存在一组 可抽出的理论最强阵容（即编号连续的 $k$ 张卡）。