裂开。。。
T1
求逆元见 https://www.cnblogs.com/lytql/p/15021752.html
然后我们考虑期望的线性性,求出每一个点都期望答案的贡献。
一个点被选中的概率其实只和第一个点\(A_1\)和当前点\(A_x\)有关,和其它的\(A\)无关。
T2
前30分随便做。
50:
发现填的数肯定单调不上升。那么之后和当前数相同的点不会产生逆序对其它都会产生。
于是我们把问题转化为:
已知:
\[\sum_{i-1}^{k}x_i=n \]求以下式子的最大值:
\[\sum_{i=1}^ka_i(n-a_i) \]显然这个式子可以化简:
\[=\sum_{i=1}^ka_in+a_i^2 \] \[=n\sum a_i-\sum a_i^2 \] \[=n^2-\sum a_i^2 \]那么我们肯定让\(a_i\)平均分配,答案最大。
70:暴力dp
100:发现这个式子可以斜率优化。优化就完了