[✗✓OI R1] 后方之水 Solution
NaCly_Fish
·
·
题解
引理：任意合并方案的总代价是相同的。
证明：追踪初始的某一堆石子，我们发现在合并的过程中，它总与其它所有堆石子都产生了一对乘积的贡献，由此得证。
由引理可知，合并的总代价就是所有 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)。