早上比赛

拿了120，并且AC了一题，可以少看一篇题解了

T1 Robert 的军队

推式子题，昨晚学的数学有用了

先看提示

我们对方差公式变形，可以得到以下两个式子

m是我们选取的士兵个数,a是士兵的身高，其实拿到这题的时候就应该想到对a进行排序，我们不妨设对于i<j时，总有ai<=aj

对于第一个式子我们可以得出我们选择的a应该是连续的，并且稍作思考或多试几个样例就能发现，我们选取的士兵个数一定为L个

但是我们不能用第一个式子计算答案，因为这样做是O(n^2)的，无法AC，我们可以用第二个式子进行计算，我们可以在排序后用前缀和处理，最后用O(n)枚举长度为L的序列，查询答案是O(1)的

为了防止计算爆double，我们把系数放到求和内，就变成了下面这个式子

这样就可以愉快地计算了

Code:

细节：s2数组的处理要先乘再除再乘，不然可能会爆

这题其实就是在求这样一个式子

看到题目后，我苦思冥想了近1hour，最后只打了个暴力，拿了20

数论这块还是太权威了，看CSDN吧，出题人的题解据说要用笛卡尔树，过于高级，显然不是最简单的解法

一片比较好的题解： LINK

Code：

细节：模数位数不要数错了

一些疑问：考试时无聊试了一下，发现这个模数是个质数，那能不能用这个性质优化呢？虽然我觉得不大行，因为里边的数相较于模数来说太小了，很难用上模数是质数的性质，但还是很好奇能不能优化

今天博客太水了，才不到600字