自动搬运

查看原文

来自洛谷，原作者为

	Coffee_zzz 沉覆z

搬运于2025-08-24 23:14:24，当前版本为作者最后更新于2025-05-07 23:41:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

定义 $p_{i,j}$ 表示位置 $i$ 和位置 $j$ 的两个小球合并在一起的概率，则转移方程为：

$$p_{i,j}=\dfrac 1 4 (p_{i,j+1}+p_{i+1,j}+p_{i+1,j+1}+p_{i,j}) $$

化简得：

$$p_{i,j}=\dfrac 1 3 (p_{i,j+1}+p_{i+1,j}+p_{i+1,j+1}) $$

其中 $p_{i,i}=1$。

定义 $f_{i,j}$ 表示第 $i$ 个小球和第 $j$ 个小球合并在一起的概率，则容易得到：

$$f_{i,j}=p_{x_i,x_j}$$

定义 $g_{i,j}$ 表示第 $i$ 个小球和第 $j$ 个小球合并在一起，且不和第 $i-1$ 个小球与第 $j+1$ 个小球合并在一起的概率，则可以得到：

$$g_{i,j}=f_{i,j}-f_{i-1,j}-f_{i,j+1}+f_{i-1,j+1}$$

定义 $s_{i,j}$ 表示第 $i$ 个小球至第 $j$ 个小球上所有数字的乘积，则答案为：

$$\sum_{i=1}^n \sum_{j=i}^n s_{i,j} \cdot g_{i,j}$$

处理出上述数组后直接计算即可。时间复杂度 $\mathcal O(n^2)$。