自动搬运

查看原文

来自洛谷，原作者为

	NaCly_Fish 北海虽赊，扶摇可接。

搬运于2025-08-24 22:43:05，当前版本为作者最后更新于2022-11-12 18:00:34，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

首先简单转化一下题意，每个位置有 $a_i$ 个棋子，每次操作选择一个棋子，将其随机向相邻位置移动。然后要选择一个目标点，使得期望操作次数最少。

设一个棋子在目标的顺时针 $i$ 格（也就是逆时针 $n-i$ 格）的位置，移到目标的期望次数为 $f_i$，则：

$$f_i=1+\frac 12 (f_{i-1}+f_{i+1}) \ \ (i\in[1,n-1]) $$

这个线性方程组可以用常系数线性递推的方法来解：

$$F(x)=2xF(x)-x^2F(x)-\frac{2x}{1-x}+(f_1+2)x$$ $$f_i=i(f_1-i+1)$$

由于 $f_n=0$，解得 $f_i=i(n-i)$。

题目要我们求出期望最小的目标点，不妨直接把所有目标的情况，全都求出答案来。

$$s_d=\sum_{i=1}^n a_i |i-d|(n-|i-d|)$$

这里有个绝对值很烦，考虑拆为：

$$b_d=\sum_{i=1}^{d-1}a_i(d-i)(n-d+i) \ , \ c_d=\sum_{i=d+1}^na_i(i-d)(n-i+d) $$

再把和式中的乘积展开，可以得到（这里以 $b$ 为例，对 $c$ 也是类似的）：

$$b_d=-\left(\sum_{i=1}^{d-1}i^2a_i \right)+(2d-n)\left(\sum_{i=1}^{d-1}ia_i \right)+d(n-d)\left(\sum_{i=1}^{d-1}a_i\right) $$

这样维护三个前缀和即可，对于 $c$ 也就是三个后缀和，做法是一致的。时间复杂度 $\Theta(n)$。

注意值域较大，需要 int128。