Fortune Wheel - Problem

题目大意

有一个上有编号 $0$ 到 $n-1$ 的转盘，你可以使转盘随机旋转到一个位置或者向前旋转 $k_i$ 个位置，求在最优策略下的期望步数。

数据范围满足，$1\le n\le 10^5,\lvert k \rvert \le 500$。

思路

考虑先使用 bfs，在 $O(n\lvert k\rvert)$ 的时间里求出从任一点通过确定步数移动到 $0$ 的最小步数。

最有策略应该是一直进行随机操作直到到达某一个临界值再使用确定步数的操作完成，所以我们可以枚举每一个临界值选取期望步数最小的一个。

假设这个临界值以内的数构成集合 $S$，那么其移动步数的期望值为 $\dfrac{(\sum\limits_{i\in S}dis_i )+n}{\lvert S\rvert}$ ，可以理解为每一次有 $\dfrac{\lvert S\rvert}{n}$ 的概率随机跳到 $S$ 以内，所以期望次数为 $\dfrac{n}{\lvert S\rvert}$。