P10323 理性（Rationality）

数学之善，统治宇宙的根本原理 —— 理性。 **** 「理性之光」伊奥，是古代精灵图形术士。已经千岁的她总能不受感情的干扰，以理性做出最优的决策。

赛时更新：请注意，对于一组确定的 $v_1,\cdots,v_n$，都可以求出 $\text{RSS}$ 的最小值。**它是关于随机变量 $v_1,\cdots,v_n$ 的一个随机变量**，将其记为 $X$，则要求的是 $\mathbb E[X]$。 笔误改正：残差平方和的英文为 $\text{RSS}$。 **** 伊奥的思绪回到了千年前的一场大战中。 她记得那场战斗中有 $n$ 个敌人，第 $i$ 个敌人在距离她 $d_i$（$d_i$ 之间互不相同）的位置上。这些敌人都带有一个**正整数**标记 $v_i$，只要以**恰好** $v_i$ 的攻击力击中它就可以将其消灭。 她只要设定一个一次函数 $f(x)=ax+b$，就能在距离她 $d_i$ 的位置放出 $f(d_i)$ 的攻击力。好在她的队友会辅助她攻击，她只用考虑确定 $a,b$ 使得 $f(x)$ 的效果最优，即最小化 $\text{RSS}$（残差平方和）： $$\text{RSS}=\sum_{i=1}^n(f(d_i)-v_i)^2$$ 当然了，这只是她的回忆。她能清晰记得每个敌人到她的距离 $d_i$，而对于 $v_i$ 她只记得满足 $l_i\leq v_i \leq r_i$。 她想知道假设每个 $v_i$ 都对应在 $[l_i,r_i]$ 范围内**均匀随机**的情况下，「$\text{RSS}$ **的最小值」的期望**。 可以证明答案总是有理数，你只需要告诉她答案对 $998244353$ 取模的结果即可。

无

无

【样例 $1$ 解释】 此样例中有 $l_i=r_i$，即情况已经确定，只需要求出此时最优的 $a,b$ 即可。容易发现 $(1,4),(3,7),(5,10)$ 这三组数据可以用一次函数完美拟合：即 $f(x)=\dfrac 32 x+\dfrac{5}{2}$，与每个点偏差都是 $0$，故 $\text{RSS}$ 最小值的期望，也就是答案为 $0$。 【样例 $2$ 解释】 这里同样有 $l_i=r_i$。$5$ 个敌人的数据 $(d_i,v_i)$ 分别为 $(1,4),(2,5),(3,7),(4,8),(9,8)$，可以证明取 $$a=\frac{87}{194} \ , \ b=\frac{911}{194}$$ 是一组使得 $\text{RSS}$ 最小的解，代入计算得 $$\text{RSS}=\sum_{i=1}^n\left( \frac{87}{194}d_i+\frac{911}{194}-v_i\right)^2=\frac{1047}{194}$$ 在模 $998244353$ 意义下答案为 $488831003$。 【数据范围】 **本题采用捆绑测试。** Subtask 1（10 pts）：$n \leq 3$； Subtask 2（10 pts）：$l_i=r_i$； Subtask 3（15 pts）：$n\le500$，$r_i\leq 500$； Subtask 4（15 pts）：$n\le 5000$； Subtask 5（20 pts）：$n\le 10^5$； Subtask 6（30 pts）：无特殊限制。 对于全部的数据，$2\le n \le 5\times 10^5$，$1\leq l_i \leq r_i \leq 10^8$，$1\leq d_i \leq 10^8$， $d_i