柿子还是得写在草稿纸上手推。
题意:很简单了,不再赘述。
做法:
首先这个权值有点抽象,我们写出来稍微化简一下。
\[\frac{1}{6^n}\sum_{x_1=1}^6\sum_{x_2=1}^6\cdots\sum_{x_n=1}^6(\sum_{i=1}^na_{i,x_i})^2 - \sum_{i=1}^nc_i
\]
这个平方一看直接 dna 动了,把他拆开,但是注意对于同一个位置的和别的统计其实不同,可以改成:
\[\frac1{6^n}(\sum_{i=1}^n\sum_{j=1,j\not=i}^n\sum_{x=1}^6\sum_{y=1}^6a_{i,x}a_{j,y}6^{n-2}+\sum_{i=1}^n\sum_{x=1}^6a_{i,x}^26^{n-1})-\sum_{i=1}^nc_i
\]
\[\frac1 {36}\sum_{i=1}^n\sum_{j=1,j\not=i}^n\sum_{x=1}^6\sum_{y=1}^6a_{i,x}a_{j,y}+\frac 1 6\sum_{i=1}^n\sum_{x=1}^6a_{i,x}^2-\sum_{i=1}^nc_i
\]
然后我们尝试把第一个式子里关于 \(i,x\) 和 \(j,y\) 的分离,当然这里需要减去补的 \(i=j\) 的情况:
\[\frac1{36}\sum_{i=1}^n\sum_{x=1}^6a_{i,x}\sum_{j=1}^n\sum_{y=1}^6a_{j,y}+\frac 1 6\sum_{i=1}^n\sum_{x=1}^6a_{i,x}^2-\sum_{i=1}^nc_i-\frac1 {36}\sum_{i=1}^n(\sum_{x=1}^6a_{i,x})^2
\]
然后我们令 \(A_i = \frac 1 6\sum\limits_{x=1}^6a_{i,x}\),柿子变成
\[(\sum\limits_{i=1}^nA_i)^2 +\frac 1 6\sum_{i=1}^n\sum_{x=1}^6a_{i,x}^2-\sum_{i=1}^nc_i-\sum_{i=1}^nA_i^2
\]
后面的整理一下,令 \(B_i=\frac{1}{6}a_{i,x}^2-c_i-A_i^2\),那么原式就变成了
\[(\sum_{i=1}^nA_i)^2+\sum_{i=1}^nB_i
\]
那么我们现在等于要解决这个柿子。
直接做相当麻烦,因为前面那个东西是二次的,那么我们不妨直接枚举 \(k=\sum\limits_{i=1}^nA_i\),这样柿子降为一次,我们可以直接统计 \(\sum\limits_{i=1}^nA_{i}k+B_i\)。
但是我们并没有办法枚举所有的 \(k\),但是我们注意到我们是要取前若干项作为答案,所以我们考虑把 \((A_i,B_i)\) 视为平面上的点,然后考虑两个点他们什么时候可以干掉对方,这个直接枚举两个点然后计算它们的斜率即可。最后我们先假设 \(k=-\infty\) 然后再逐步调大就可以了。