自动搬运

查看原文

来自洛谷，原作者为

	NULL1F1CAT10N Recursion / Dispersion / Destruction

搬运于2025-08-24 22:56:55，当前版本为作者最后更新于2024-04-24 19:46:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Link

考虑对一组固定的 $v_i$ 求 $RSS$ 最小值。

先将 $RSS$ 转换为关于 $a$ 的形式：

$RSS=\sum\limits_{i=1}^n(ad_i+b-v_i)^2=(\sum\limits_{i=1}^nd_i^2)a^2+2(\sum\limits_{i=1}^nd_i(b-v_i))a+(\sum\limits_{i=1}^n(b-v_i)^2)$

由 $n\sum\limits_{i=1}^nd_i^2\neq(\sum\limits_{i=1}^nd_i)^2$ 知 $d_i$ 不全相等，故 $\sum\limits_{i=1}^nd_i^2>0$，故此处 $a=-\frac{\sum\limits_{i=1}^nd_i(b-v_i)}{\sum\limits_{i=1}^nd_i^2}$ 取最小值。

将此时的 $RSS$ 转换为关于 $b$ 的形式：

此时 $RSS=\frac{1}{\sum\limits_{i=1}^nd_i^2}(\sum\limits_{i=1}^nd_i^2\sum\limits_{i=1}^n(b-v_i)^2-(\sum\limits_{i=1}^nd_i(b-v_i))^2)=\frac{(n\sum\limits_{i=1}^nd_i^2-(\sum\limits_{i=1}^nd_i)^2)b^2-2(\sum\limits_{i=1}^nv_i\sum\limits_{i=1}^nd_i^2-\sum\limits_{i=1}^nd_i\sum\limits_{i=1}^nd_iv_i)b+(\sum\limits_{i=1}^nd_i^2\sum\limits_{i=1}^nv_i^2-(\sum\limits_{i=1}^nd_iv_i)^2)}{\sum\limits_{i=1}^nd_i^2}$ 为一个关于 $b$ 的二次函数。

由题 $n\sum\limits_{i=1}^nd_i^2-(\sum\limits_{i=1}^nd_i)^2\neq0$ 且由柯西不等式知 $n\sum\limits_{i=1}^nd_i^2-(\sum\limits_{i=1}^nd_i)^2\ge0$。

故取 $b=\frac{\sum\limits_{i=1}^nv_i\sum\limits_{i=1}^nd_i^2-\sum\limits_{i=1}^nd_i\sum\limits_{i=1}^nd_iv_i}{n\sum\limits_{i=1}^nd_i^2-(\sum\limits_{i=1}^nd_i)^2}$ 可使 $RSS$ 最小。

此时 $RSS=-\frac{(\sum\limits_{i=1}^nv_i\sum\limits_{i=1}^nd_i^2-\sum\limits_{i=1}^nd_i\sum\limits_{i=1}^nd_iv_i)^2}{(n\sum\limits_{i=1}^nd_i^2-(\sum\limits_{i=1}^nd_i)^2)\sum\limits_{i=1}^nd_i^2}+\frac{\sum\limits_{i=1}^nd_i^2\sum\limits_{i=1}^nv_i^2-(\sum\limits_{i=1}^nd_iv_i)^2}{\sum\limits_{i=1}^nd_i^2}$。

此时的 $\mathbb{E}[RSS]$ 即为所求。

注意到 $d_i$ 固定，也就是说 $-\frac{1}{(n\sum\limits_{i=1}^nd_i^2-(\sum\limits_{i=1}^nd_i)^2)\sum\limits_{i=1}^nd_i^2}$，$\sum\limits_{i=1}^nd_i$ 和 $\sum\limits_{i=1}^nd_i^2$ 都是固定的。

即求 $\mathbb{E}[(\sum\limits_{i=1}^nv_i\sum\limits_{i=1}^nd_i^2-\sum\limits_{i=1}^nd_i\sum\limits_{i=1}^nd_iv_i)^2]$ 和 $\mathbb{E}[\sum\limits_{i=1}^nv_i^2]$ 以及 $\mathbb{E}[(\sum\limits_{i=1}^nd_iv_i)^2]$。

$\mathbb{E}[\sum\limits_{i=1}^nv_i^2]=\sum\limits_{i=1}^n\mathbb{E}[v_i^2]=\sum\limits_{i=1}^n(\frac{1}{r_i-l_i+1}\sum\limits_{j=l_i}^{r_i}j^2)=\sum\limits_{i=1}^n\frac{r_i(r_i+1)(2r_i+1)-l_i(l_i-1)(2l_i-1)}{6(r_i-l_i+1)}$。

$\mathbb{E}[(\sum\limits_{i=1}^nd_iv_i)^2]=\mathbb{E}[\sum\limits_{i=1}^nd_i^2v_i^2]+2\mathbb{E}[\sum\limits_{1\le i<j\le n}d_id_jv_iv_j]=\sum\limits_{i=1}^nd_i^2\mathbb{E}[v_i^2]+2\sum\limits_{1\le i<j\le n}d_i\mathbb{E}[v_i]d_j\mathbb{E}[v_j]=\sum\limits_{i=1}^nd_i^2\mathbb{E}[v_i^2]+(\sum\limits_{i=1}^nd_i\mathbb{E}[v_i])^2-\sum\limits_{i=1}^nd_i^2\mathbb{E}[v_i]^2$， 其中 $\mathbb{E}[v_i]=\frac{r_i(r_i+1)-l_i(l_i-1)}{2(r_i-l_i+1)}$。

$\mathbb{E}[(\sum\limits_{i=1}^nv_i\sum\limits_{i=1}^nd_i^2-\sum\limits_{i=1}^nd_i\sum\limits_{i=1}^nd_iv_i)^2]=(\sum\limits_{i=1}^nd_i^2)^2\mathbb{E}[(\sum\limits_{i=1}^nv_i)^2]+(\sum\limits_{i=1}^nd_i)^2\mathbb{E}[(\sum\limits_{i=1}^nd_iv_i)^2]-2\sum\limits_{i=1}^nd_i^2\sum\limits_{i=1}^nd_i\mathbb{E}[\sum\limits_{i=1}^nv_i\sum\limits_{i=1}^nd_iv_i]$，其中 $\mathbb{E}[(\sum\limits_{i=1}^nd_iv_i)^2]$ 已计算过，只需考虑 $\mathbb{E}[\sum\limits_{i=1}^nv_i\sum\limits_{i=1}^nd_iv_i]$ 和 $\mathbb{E}[(\sum\limits_{i=1}^nv_i)^2]$。

类似 $\mathbb{E}[(\sum\limits_{i=1}^nd_iv_i)^2]$，可以得出 $\mathbb{E}[(\sum\limits_{i=1}^nv_i)^2]=\sum\limits_{i=1}^n\mathbb{E}[v_i^2]+(\sum\limits_{i=1}^n\mathbb{E}[v_i])^2-\sum\limits_{i=1}^n\mathbb{E}[v_i]^2$，$\mathbb{E}[\sum\limits_{i=1}^nv_i\sum\limits_{i=1}^nd_iv_i]=\sum\limits_{i=1}^nd_i\mathbb{E}[v_i^2]+\sum\limits_{i=1}^n\mathbb{E}[v_i]\sum\limits_{i=1}^nd_i\mathbb{E}[v_i]-\sum\limits_{i=1}^nd_i\mathbb{E}[v_i]^2$。

最后计算出各式代入原式即可。代码有些凌乱，变量名命名可参考注释。

#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int ksm(int a, int b, int p = mod) {
	int ret = 1;
	while(b) {
		if(b & 1) {
			ret = 1ll * ret * a % p;
		}
		a = 1ll * a * a % p;
		b >>= 1;
	}
	return ret;
}
int inv(int a, int p = mod) {
	return ksm(a, p - 2, p);
}
int n, d[500005], l[500005], r[500005], inv2, inv6;
int Evv[500005], Evd[500005], Etop, Sdd, Sevv, Sevd2, Sd, ESv2, ESvd2, ESvSvd, Ev[500005], SEv, SEv2, Sevdd, Sevd, Svvd, S;
/*
Evv_i = E[v_i^2]
Evd_i = E[v_id_i]=d_iE[v_i]
Ev_i = E[v_i]
下记 \sum\limits_{i=1}^n 为 Sum
Etop = E[(Sum(v)Sum(d^2)-Sum(d)Sum(vd))^2]
Sdd = Sum(d^2)
Sevv = Sum(E[v^2]) = E[Sum(v^2)]
Sevd2 = Sum(E[(vd)^2])
Sd = Sum(d)
ESv2 = E[Sum(v)^2]
ESvd2 = E[Sum(vd)^2]
ESvSvd = E[Sum(v)Sum(vd)]
SEv = Sum(E[v])
SEv2 = Sum(E[v]^2)
Sevdd = Sum(E[vd]^2)
Sevd = Sum(E[vd])
Svvd = Sum(dE[v^2])
S = Sum(E[vd]E[v])
*/
signed main() {
	cin >> n;
	inv2 = inv(2);
	inv6 = inv(6);
	for(int i = 1; i <= n; ++i) {
		cin >> d[i] >> l[i] >> r[i];
		Sdd += 1ll * d[i] * d[i] % mod;
		Sdd %= mod;
		Sd += d[i];
		Sd %= mod;
		Ev[i] = 1ll * (l[i] + r[i]) % mod * inv2 % mod;
		SEv += Ev[i];
		SEv2 += 1ll * Ev[i] * Ev[i] % mod;
		SEv %= mod;
		SEv2 %= mod;
		Evd[i] = 1ll * d[i] * (l[i] + r[i]) % mod * inv2 % mod;
		Evv[i] = 1ll * ((1ll * r[i] * (r[i] + 1) % mod * (2 * r[i] + 1) % mod - 1ll * l[i] * (l[i] - 1) % mod * (2 * l[i] - 1) % mod) + mod) * inv(r[i] - l[i] + 1) % mod * inv6 % mod;
		Sevv += Evv[i];
		Sevd += Evd[i];
		S += 1ll * Evd[i] * Ev[i] % mod;
		Sevd2 += 1ll * Evv[i] * d[i] % mod * d[i] % mod;
		Sevdd += 1ll * Evd[i] * Evd[i] % mod;
		Svvd += 1ll * Evv[i] * d[i] % mod;
		Sevv %= mod;
		Sevd %= mod;
		Sevd2 %= mod;
		Sevdd %= mod;
		Svvd %= mod;
		S %= mod;
	}
	ESv2 = ((Sevv + 1ll * SEv * SEv - SEv2) % mod + mod) % mod;
	ESvd2 = ((Sevd2 + 1ll * Sevd * Sevd - Sevdd) % mod + mod) % mod;
	ESvSvd = ((Svvd + 1ll * Sevd * SEv - S) % mod + mod) % mod;
	Etop = (1ll * ESv2 * Sdd % mod * Sdd % mod + 1ll * Sd * Sd % mod * ESvd2 % mod - 2ll * Sdd * Sd % mod * ESvSvd % mod) % mod;
	Etop = (Etop + mod) % mod;
	cout << 1ll * (1ll * Sdd * Sevv - ESvd2 - 1ll * Etop * inv((1ll * n * Sdd - 1ll * Sd * Sd) % mod) % mod + mod) % mod * inv(Sdd) % mod << endl;
	return 0;
}