[G22CR1] D.桎梏的救赎——题解

· · 个人记录

一道大水题，直接放代码

[传送门] (https://www.luogu.com.cn/paste/h2ms3uxk)

ok各位看完代码应该就明白了吧……

其实救赎值与你救赎的顺序无关（提示的很明显了吧）

非要讲讲的话，那就是这么一个东西了

如果按一个从前往后取的话（以五个为例），那么画出的图形是一个三角形（因为自己减自己是0，所以不用画上）

如果按1,4,2,5,3的顺序取的话，那么经过移动可以称为一个三角形

如上图

再来，按别的顺序呢

4,5,3,2,1？

很显然，仍然能通过移动得到一个三角形

也就是说，救赎值与救赎的顺序无关

于是，问题转化为求\sum_{i=1}^n\sum_{j=1}^i(ai-aj)^2 的值

然后可以进一步化为1/2\sum_{i=1}^n\sum_{j=1}^n(ai-aj)^2

再除以n^2得到:

1/2n^2\sum_{i=1}^n\sum_{j=1}^n(ai-aj)^2

将这个式子拆开

1/2n^2\sum_{i=1}^n\sum_{j=1}^n(ai-aj)^2

=1/2n^2\sum_{i=1}^n\sum_{j=1}^nai^2+aj^2-2*ai*aj

=1/2n^2\sum_{i=1}^n(n*ai^2+\sum_{j=1}^naj^2-2*ai*\sum_{j=1}^naj)

=1/2n^2(n*\sum_{i=1}^nai^2+n*\sum_{i=1}^nai^2-2*\sum_{i=1}^nai*\sum_{i=1}^nai)

=1/n\sum_{i=1}^nai^2-2*[(\sum_{i=1}^nai)/n]^2

实际上就是求个方差

为什么除n^2呢，因为为了凑方差