题解：「Ynoi2009」rprsvq

Y n o i 数 数 题

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

\[\begin{align} &\frac{\sum a_i^2 - 2\sum a_i \cdot \bar{a} + \sum\bar{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_i\right)^2&\\end{align} \]

用 \(S\) 表示一个下标集合，这样答案就可以表示成：

\[\sum_{S\in \{1,2,3,\dots,n\}} \frac{1}{|S|}\left(\sum_{i\in S} a_i^2\right) - \frac{1}{|S|}\left(\sum_{i\in S} a_i\right) ^ 2 \]

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

\[\begin{align} &\sum_k \frac{1}{k} {n - 1\choose 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 {n\choose 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\) 和 \(i\neq 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 {n\choose 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 - 1\choose k - 1}&\=& \frac{1}{n} + \frac{2^n - 2}{n}&\=& \frac{2^n - 1}{n}&\\end{align} \]

2. \(i\neq j\)

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

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

答案就是：

\[\frac{2^n - 1}{n} F - \frac{F\cdot f(len)}{len} - \frac{2^n - 1 - f(len)}{len\cdot (len - 1)} (G^2 - F) \]

时间复杂度 \(\mathcal{O}(m\log n)\) .