Solution. CF1951G Clacking Balls
Description
有 $m$ 个篮子放在一个环上,篮子按顺时针顺序编号为 $1\sim m$。有 $n$ 个球,第 $i$ 个球放在篮子 $a_i$ 中,$a_i$ 互不相同。接下来反复进行如下操作:从 $1\sim n$ 中等概率选出一个数 $i$,若球 $i$ 已被扔掉则什么都不做;否则将球 $i$ 移动到顺时针方向的下一个篮子里,如果下一个篮子里本来有一个球 $j$,则将球 $j$ 扔掉。进行一次上述操作总是花费 $1$ 单位时间,所有篮子中只剩下一个球时结束此过程。求过程持续的期望时间,答案对 $10^9 + 7$ 取模。
$1\le n\le 3\times 10^5, n\le m\le 10^9$