P12293 [蓝桥杯 2024 国 Java A] 合并小球 题解

· · 题解

定义 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)。