• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

题解:「Ynoi2009」rprsvq

开发技术 开发技术 2周前 (05-03) 6次浏览

题面 Link

Y n o i 数 数 题

先化一下单次方差的式子:

[begin{align}
&frac{sum a_i^2 – 2sum a_i cdot bar{a} + sumbar{a}^2}{n}&\
=&frac{1}{n}sum a_i^2 – frac{2}{n} sum a_i bar{a} + bar{a}^2&\
=&frac{1}{n}sum a_i^2 – frac{1}{n^2} left(sum a_iright)^2&\
end{align}
]

(S) 表示一个下标集合,这样答案就可以表示成:

[sum_{Sin {1,2,3,dots,n}} frac{1}{|S|}left(sum_{iin S} a_i^2right) – frac{1}{|S|}left(sum_{iin S} a_iright) ^ 2
]

先搞前面的式子,考虑枚举集合大小 (k) 和每个元素的贡献,计数的时候可以用钦定法解决,可以得到:

[begin{align}
&sum_k frac{1}{k} {n – 1choose k – 1} sum_{i=1}^n a_i^2&\
=&sum_k frac{1}{k} frac{(n – 1)!}{(k – 1)!(n – k)!} sum_{i=1}^n a_i^2&\
=&frac{1}{n} sum_k {nchoose k} sum_{i=1}^n a_i^2&\
=&frac{2^n – 1}{n} sum_{i=1}^n a_i^2&\
end{align}
]

再搞后面的式子,先把平方写成 (sum_{i=1}^n sum_{j=1}^n a_i a_j) ,对于 (i=j)(ineq j) 的情况分类讨论算贡献。

  1. (i = j)
[begin{align}
&sum_k frac{1}{k^2} {n – 1 choose k – 1} sum_{i=1}^n a_i^2&\
=&sum_k frac{1}{k^2} frac{(n-1)!}{(k-1)!(n-k)!} sum_{i=1}^n a_i^2&\
=&frac{1}{n} sum_k frac{1}{k} frac{n!}{k!(n – k)!} sum_{i=1}^n a_i^2&\
=&frac{1}{n} f(n) cdot sum_{i=1}^n a_i^2&\
end{align}
]

其中 (f(n) = sum_k frac{1}{k} {n choose k}) .

考虑预处理,考虑差分:

[begin{align}
f(n) – f(n – 1) =& frac{1}{n}cdot {nchoose n} + sum_{i=1}^{n – 1} frac{1}{k} cdot left({n choose k} – {n choose k – 1}right)&\
=& frac{1}{n} + sum_{i=1}^{n – 1} frac{1}{k} {n – 1choose k – 1}&\
=& frac{1}{n} + frac{2^n – 2}{n}&\
=& frac{2^n – 1}{n}&\
end{align}
]

  1. (ineq j)
[begin{align}
&sum_k frac{1}{k^2} {n – 2choose k – 2} left(left(sum_{i=1}^n a_iright) ^ 2 – sum_{i=1}^n a_i^2right)&\
=&sum_k frac{1}{k^2} frac{(n-2)!}{(k-2)!(n-k)!}left(left(sum_{i=1}^n a_iright) ^ 2 – sum_{i=1}^n a_i^2right)&\
=&frac{1}{ncdot (n – 1)} sum_k frac{k – 1}{k} frac{n!}{k!(n – k)!}left(left(sum_{i=1}^n a_iright) ^ 2 – sum_{i=1}^n a_i^2right)&\
=&frac{1}{ncdot (n – 1)} sum_k left({nchoose k} – frac{{nchoose k}}{k}right) left(left(sum_{i=1}^n a_iright) ^ 2 – sum_{i=1}^n a_i^2right)&\
=&frac{2 ^ n – 1 – f(n)}{ncdot (n – 1)}left(left(sum_{i=1}^n a_iright) ^ 2 – sum_{i=1}^n a_i^2right)&\
end{align}
]

然后用线段树维护一下 (F = sum_{i=l}^r a_i)(G = sum_{i=l}^2 a_i^2) .

答案就是:

[frac{2^n – 1}{n} F – frac{Fcdot f(len)}{len} – frac{2^n – 1 – f(len)}{lencdot (len – 1)} (G^2 – F)
]

时间复杂度 (mathcal{O}(mlog n)) .


程序员灯塔
转载请注明原文链接:题解:「Ynoi2009」rprsvq
喜欢 (0)