AT5741 题解
$\text{Description}$
数轴上有 $n$ 只史莱姆，第 $i$ 只史莱姆的位置为 $x_i$。
保证 $1\le x_1\le x_2\le \cdots\le x_n\le 10^9$。
Niwango 要进行 $n-1$ 次操作，第 $i$ 次操作的过程如下：
- 在 $[1,n-i]$ 中等概率随机选取一个整数 $k$。
- 将从左至右第 $k$ 只史莱姆移至其右边距其最近的史莱姆处，并合并为一只史莱姆。
你需要求出这 $n-1$ 次操作的过程中，Niwango 每次移动史莱姆的距离和的期望与 $(n-1)!$ 的乘积对 $10^9+7$ 取模后的值。
形式化地，设你的答案为 $A$，则你需要输出 。
$\text{Solution}$
想了半天往错误的方向想了……
首先我们有 $E(\sum a_i)=\sum E(a_i)$，考虑将最终所求的 $A$ 分解为若干段 $x_{i+1}-x_i$ 的期望。
其次，我们认为一段 $x_{i+1}-x_{i}$ 被第 $j$ 个史莱姆走过当且仅当第 $j$ 个史莱姆是直接被移到第 $i+1$ 个史莱姆或更后面的史莱姆处的。这里的第几个指的是初始局面意义下的第几个。
那么记 $p_{i-j,i}$ 表示第 $i-j$ 个史莱姆走过 $x_{i+1}-x_i$ 这一段的概率，容易有 $p_{i-j,i}=\frac{1}{j+1}$，这是因为这个史莱姆必须在 $[i-j+1,i]$ 内的史莱姆全部都进行过移动后才进行移动的，也就是说它必须在第 $j+1$ 次或更后面才被移动，同时，按照题目中的选法，实际上任意一种选法都唯一对应一个排列，且任意选法概率相同，故有：
所以答案为：
$\text{Code}$
1 |
|