菜王的 blog

初中二次函数题最有用的一集。

将 $f(x) = ax + b$ 展开，我们可以得到以下的式子：

$\sum_{i = 1}^n (d_i \times a + b - v_i)^2\\$

这个东西在 $b$ 取任意一个值的时候，都是一个关于 $a$ 的二次函数：

$\sum_{i = 1}^n d_i^2 a^2 + 2(b - v_i)d_i \times a + (b - v_i)^2\\$

这个函数的二次项始终为正数，于是当 $a$ 取对称轴时函数取到最小值：

$a = \frac{\sum_{i = 1}^n (v_i - b)d_i}{\sum_{i = 1}^n d_i^2}\\ \left(\sum_{i = 1}^n d_i^2\right)\left(\frac{\sum_{i = 1}^n (v_i - b)d_i}{\sum_{i = 1}^n d_i^2}\right)^2 + 2\left(\sum_{i = 1}^n (b - v_i)d_i\right)\left(\frac{\sum_{i = 1}^n (v_i - b)d_i}{\sum_{i = 1}^n d_i^2}\right) + \left(\sum_{i = 1}^n (b - v_i)^2\right)\\ \frac{(\sum_{i = 1}^n v_id_i)^2 - 2(\sum_{i = 1}^n v_id_i)(b\sum_{i = 1}^n d_i) + b^2(\sum_{i = 1}^n d_i)^2}{\sum_{i = 1}^n d_i^2} + 2\left(b \sum_{i = 1}^n d_i - \sum_{i = 1}^n v_id_i\right)\left(\frac{\sum_{i = 1}^n v_id_i - b \sum_{i = 1}^n d_i}{\sum_{i = 1}^n d_i^2}\right) + \left(\sum_{i = 1}^n b^2 - 2bv_i + v_i^2\right)\\ svd = \sum_{i = 1}^n v_id_i, sd = \sum_{i = 1}^n d_i, sd2 = \sum_{i = 1}^n d_i^2, sv = \sum_{i = 1}^n v_i, sv2 = \sum_{i = 1}^n v_i^2\\ nb^2 - 2sv \times b + sv2 - \frac{b^2 \times sd^2 - 2svd \times sd \times b + svd^2}{sd2}\\ \left(n - \frac{sd^2}{sd2}\right)b^2 + 2\left(\frac{svd \times sd}{sd2} - sv\right)b + sv2 - \frac{svd^2}{sd2}\\$

代入后得到了一个只与 $b$ 有关的二次函数。然后我们需要判断 $n - \frac{sd^2}{sd2}$ 的正负性，但是这是容易证明一定 $\ge 0$ 的。

$n - \frac{sd^2}{sd2} \ge 0\\ n \ge \frac{sd^2}{sd2}\\ nsd2 \ge sd^2\\ n\sum_{i = 1}^n d_i^2 \ge \left(\sum_{i = 1}^n d_i\right)^2\\ n\sum_{i = 1}^n d_i^2 \ge \sum_{1 \le i, j \le n} d_i d_j\\ (n - 1)\sum_{i = 1}^n d_i^2 \ge \sum_{1 \le i, j \le n, i \ne j} d_i d_j\\ \sum_{1 \le i, j \le n, i \ne j}^n d_i^2 - \sum_{1 \le i, j \le n, i \ne j} d_i d_j \ge 0\\ \sum_{1 \le i, j \le n, i \ne j}^n d_i^2 - d_i d_j \ge 0\\ \sum_{1 \le i < j \le n}^n d_i^2 + d_j ^ 2 - 2 d_i d_j \ge 0\\$

而对于任意两个正整数 $x, y$ 都显然有 $x^2 + y^2 \ge 2xy$（$(x - y)^2 \ge 0$），于是结论成立。又因为题目保证 $n - \frac{sd^2}{sd2} > 0$，所以不会出现除 $0$ 的情况，$b$ 取对称轴时函数取到最小值。

$b = \frac{sv - \frac{svd \times sd}{sd2}}{n - \frac{sd^2}{sd2}}\\ sv2 - \frac{svd^2}{sd2} - \frac{(sv - \frac{svd \times sd}{sd2})^2}{n - \frac{sd^2}{sd2}}\\ sv2 - \frac{svd^2}{sd2} - \frac{sv^2 - 2sv\frac{svd \times sd}{sd2} + \left(\frac{svd \times sd}{sd2}\right)^2}{n - \frac{sd^2}{sd2}}\\ sv2 - \frac{svd^2}{sd2} - \left(\frac{sv^2}{n - \frac{sd^2}{sd2}} - 2\frac{\frac{sd}{sd2}}{n - \frac{sd^2}{sd2}}sv \times svd + \frac{\left(\frac{sd}{sd2}\right)^2}{n - \frac{sd^2}{sd2}}svd^2\right)\\ sv2 - \frac{svd^2}{sd2} - \frac{\left(\frac{sd}{sd2}\right)^2}{n - \frac{sd^2}{sd2}}svd^2 - \frac{sv^2}{n - \frac{sd^2}{sd2}} + 2\frac{\frac{sd}{sd2}}{n - \frac{sd^2}{sd2}}sv \times svd\\$

于是我们得到了，对于一个固定的 $v$，代价的最小值是这么一坨东西。而 $sd, sd2$ 都是已知的，所以只需要求出 $sv2, svd^2, sv^2, sv \times svd$ 的期望即可。代入第一个 $v$ 固定的样例，虽然中间涉及到的数很大，但是最后答案是 $0$，和样例输出相符合！

具体怎么求呢？先考虑 $sv2$。根据期望的线性性，显然有：

$sv2 = \sum_{i = 1}^n \frac{S_2(l_i, r_i)}{r_i - l_i + 1}$

直接计算即可。

考虑设状态 $f_{i, 0 / 1 / 2 / 3 / 4}$ 分别表示 $sv, svd, sv^2, sv \times svd, svd^2$ 只考虑前 $i$ 项的期望，可以推导出转移方程：

$f_{i, 0} = f_{i - 1, 0} + \frac{l_i + r_i}2\\ f_{i, 1} = f_{i - 1, 1} + d_i\frac{l_i + r_i}2\\ f_{i, 2} = f_{i - 1, 2} + (l_i + r_i)f_{i - 1, 0} + \frac{S_2(l_i, r_i)}{r_i - l_i + 1}\\ f_{i, 3} = f_{i - 1, 3} + \frac{l_i + r_i}2f_{i - 1, 1} + d_i\frac{l_i + r_i}2f_{i - 1, 0} + d_i\frac{S_2(l_i, r_i)}{r_i - l_i + 1}\\ f_{i, 4} = f_{i - 1, 4} + d_i(l_i + r_i)f_{i - 1, 1} + d_i^2\frac{S_2(l_i, r_i)}{r_i - l_i + 1}\\$

然后可以 $O(n)$ 递推，但是计算逆元需要 $O(n \log mod)$。这题就做完了。

对着式子写就能过的题，应该不会有人要代码吧？