自动搬运

查看原文

来自洛谷，原作者为

	NaCly_Fish 北海虽赊，扶摇可接。

搬运于2025-08-24 22:34:34，当前版本为作者最后更新于2021-11-13 21:20:50，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

引理：任意合并方案的总代价是相同的。

证明：追踪初始的某一堆石子，我们发现在合并的过程中，它总与其它所有堆石子都产生了一对乘积的贡献，由此得证。

由引理可知，合并的总代价就是所有 $a_i\times a_j \ (i<j)$ 的和，因此所有情况的代价之和就是

$$[x^2]\sum_{a_1+\cdots+a_n=S }\prod_{i=1}^n(a_ix+1)[a_i>0] $$$$=[x^2y^S]\left( \sum_{i=1}^\infty (ix+1)y^i\right)^n $$

好在这个二元 GF 非常简单，分两部分求和化为

$$[x^2y^S]\left( \frac{xy}{(1-y)^2}+\frac{y}{1-y}\right)^n $$$$=[x^2y^{S-n}]\frac{(x+(1-y))^n}{(1-y)^{2n}}$$

把不含 $x$ 的项提出来就是

$$[y^{S-n}](1-y)^{-2n}[x^2](x+(1-y))^n$$ $$=[y^{S-n}](1-y)^{-2n} \binom n2(1-y)^{n-2}$$ $$=\binom n2 [y^{S-n}](1-y)^{-(n+2)}$$ $$=\binom n2 \binom{S+1}{n+1}$$

直接 $\Theta(n)$ 计算即可通过，当然也可以做到 $\Theta(\sqrt n \log n)$。