[JRKSJ R5] Jalapeno and Garlic

· · 题解

首先简单转化一下题意，每个位置有 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。