CF1951G.Clacking Balls

Rammstein - Ausländer

ඞ

有 $m$ 个篮子沿着一个圆圈顺时针排列，编号为 $1$ 到 $m$（第 $m$ 号篮子与第 $1$ 号篮子相邻）。此外，有 $n$ 个球，第 $i$ 个球最初放在第 $a_i$ 号篮子中，且每个篮子最多只含有一个球。

Alice 可以进行如下操作，每次操作无论是否移动/扔掉球都恰好耗时一秒：

• Alice 从 $1$ 到 $n$ 中等概率随机选择一个整数 $i$。
• 如果第 $i$ 个球已经被扔掉，则什么也不做。
• 否则，将第 $i$ 个球从当前所在的篮子移动到下一个篮子（顺时针方向）。如果目标篮子中已经有另一个球 $j$，则将球 $j$ 扔掉。

她重复上述操作，直到只剩下一个球为止。请计算 Alice 结束该过程所需的期望时间（单位为秒）。

可以证明，答案可以表示为最简分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 互质。你需要输出 $p \cdot q^{-1} \bmod 10^9 + 7$。可以保证 $10^9 + 7 \nmid q$。

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 10^4$）——表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 3 \cdot 10^5, n \le m \le 10^9$）——球的数量和篮子的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le m$，$a_i$ 两两不同）——每个球的初始位置。

保证所有测试用例中 $n$ 的总和不超过 $3 \cdot 10^5$。

对于每个测试用例，输出一个整数：Alice 结束该过程所需的期望时间（单位为秒），对 $10^9 + 7$ 取模。

在第一个测试用例中，Alice 可能的操作如下（若球 $i$ 已被扔掉，则定义 $a_i = -1$）：

• 初始时，$a = [5, 1, 4]$。
• Alice 以 $\frac{1}{3}$ 的概率选择 $i = 2$，将球 $2$ 移动到篮子 $2$。此时 $a = [5, 2, 4]$。
• Alice 以 $\frac{1}{3}$ 的概率选择 $i = 2$，将球 $2$ 移动到篮子 $3$。此时 $a = [5, 3, 4]$。
• Alice 以 $\frac{1}{3}$ 的概率选择 $i = 2$，将球 $2$ 移动到篮子 $4$。由于篮子 $4$ 原本有球 $3$，球 $3$ 被扔掉。此时 $a = [5, 4, -1]$。
• Alice 以 $\frac{1}{3}$ 的概率选择 $i = 3$。球 $3$ 已被扔掉，什么也不做。此时 $a = [5, 4, -1]$。
• Alice 以 $\frac{1}{3}$ 的概率选择 $i = 2$，将球 $2$ 移动到篮子 $5$，球 $1$ 被扔掉。此时 $a = [-1, 5, -1]$，过程结束。

本测试用例的答案为 $\frac{189}{5}$。第二个测试用例的答案为 $14$（注意这两个球最初相邻）。

第三个测试用例的答案为 $35$。

第四个测试用例的答案为 $\frac{220}{3}$。

第五个测试用例中，初始时只有一个球，答案为 $0$。

由 ChatGPT 4.1 翻译