{"problem":{"name":"理性（Rationality）","description":{"content":"赛时更新：请注意，对于一组确定的 $v_1,\\cdots,v_n$，都可以求出 $\\text{RSS}$ 的最小值。**它是关于随机变量  $v_1,\\cdots,v_n$ 的一个随机变量**，将其记为 $X$，则要求的是 $\\mathbb E[X]$。    笔误改正：残差平方和的英文为 $\\text{RSS}$。 **** 伊奥的思绪回到了千年前的一场大战中。 她记得那场战斗中有 $n$ 个","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10323"},"statements":[{"statement_type":"Markdown","content":"赛时更新：请注意，对于一组确定的 $v_1,\\cdots,v_n$，都可以求出 $\\text{RSS}$ 的最小值。**它是关于随机变量  $v_1,\\cdots,v_n$ 的一个随机变量**，将其记为 $X$，则要求的是 $\\mathbb E[X]$。   \n笔误改正：残差平方和的英文为 $\\text{RSS}$。\n****\n伊奥的思绪回到了千年前的一场大战中。\n\n她记得那场战斗中有 $n$ 个敌人，第 $i$ 个敌人在距离她 $d_i$（$d_i$ 之间互不相同）的位置上。这些敌人都带有一个**正整数**标记 $v_i$，只要以**恰好** $v_i$ 的攻击力击中它就可以将其消灭。\n\n她只要设定一个一次函数 $f(x)=ax+b$，就能在距离她 $d_i$ 的位置放出 $f(d_i)$ 的攻击力。好在她的队友会辅助她攻击，她只用考虑确定 $a,b$ 使得 $f(x)$ 的效果最优，即最小化 $\\text{RSS}$（残差平方和）：\n$$\\text{RSS}=\\sum_{i=1}^n(f(d_i)-v_i)^2$$\n当然了，这只是她的回忆。她能清晰记得每个敌人到她的距离 $d_i$，而对于 $v_i$ 她只记得满足 $l_i\\leq v_i \\leq r_i$。\n\n她想知道假设每个 $v_i$ 都对应在 $[l_i,r_i]$ 范围内**均匀随机**的情况下，「$\\text{RSS}$ **的最小值」的期望**。   \n可以证明答案总是有理数，你只需要告诉她答案对 $998244353$ 取模的结果即可。\n\n## Input\n\n第一行一个正整数 $n$，表示敌人的个数。  \n接下来 $n$ 行，每行三个正整数 $d_i,l_i,r_i$，分别表示第 $i$ 个敌人到伊奥的距离，其标记 $v_i$ 的下界和上界。\n\n为了方便你的计算，伊奥保证 $d_i< d_{i+1}$（$1\\leq i <n$），并且：\n\n$$n\\sum_{i=1}^nd_i^2 \\not \\equiv \\left(\\sum_{i=1}^nd_i \\right)^2 \\pmod{998244353}$$\n**即确保答案在模 $998244353$ 意义下一定存在。**\n\n## Output\n\n输出一行一个整数，表示所有情况下 $\\text{RSS}$ 最小值的期望。\n\n[samples]\n\n## Background\n\n数学之善，统治宇宙的根本原理 —— 理性。\n****\n「理性之光」伊奥，是古代精灵图形术士。已经千岁的她总能不受感情的干扰，以理性做出最优的决策。   \n\n## Note\n\n【样例 $1$ 解释】\n\n此样例中有 $l_i=r_i$，即情况已经确定，只需要求出此时最优的 $a,b$ 即可。容易发现 $(1,4),(3,7),(5,10)$ 这三组数据可以用一次函数完美拟合：即 $f(x)=\\dfrac 32 x+\\dfrac{5}{2}$，与每个点偏差都是 $0$，故 $\\text{RSS}$ 最小值的期望，也就是答案为 $0$。\n\n【样例 $2$ 解释】\n\n这里同样有 $l_i=r_i$。$5$ 个敌人的数据 $(d_i,v_i)$ 分别为 $(1,4),(2,5),(3,7),(4,8),(9,8)$，可以证明取\n$$a=\\frac{87}{194} \\ , \\ b=\\frac{911}{194}$$\n是一组使得 $\\text{RSS}$ 最小的解，代入计算得\n$$\\text{RSS}=\\sum_{i=1}^n\\left( \\frac{87}{194}d_i+\\frac{911}{194}-v_i\\right)^2=\\frac{1047}{194}$$\n在模 $998244353$ 意义下答案为 $488831003$。\n\n【数据范围】\n\n**本题采用捆绑测试。**\n\nSubtask 1（10 pts）：$n \\leq 3$；  \nSubtask 2（10 pts）：$l_i=r_i$；  \nSubtask 3（15 pts）：$n\\le500$，$r_i\\leq 500$；  \nSubtask 4（15 pts）：$n\\le 5000$；  \nSubtask 5（20 pts）：$n\\le 10^5$；  \nSubtask 6（30 pts）：无特殊限制。\n\n对于全部的数据，$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<d_{i+1}$（$1\\leq i <n$），并且有：\n$$n\\sum_{i=1}^nd_i^2 \\not \\equiv \\left(\\sum_{i=1}^nd_i \\right)^2 \\pmod{998244353}$$\n\n【提示】\n\n题目中要求出「$\\text{RSS}$ 的最小值」期望值。对于离散随机变量 $X$，假设其可以取值为 $a_1,a_2,\\cdots,a_n$，对应概率为 $p_1,p_2,\\cdots,p_n$（$p_1+\\cdots+p_n=1$），则其期望值可以定义为：\n$$\\mathbb E[X]=\\sum_{i=1}^np_i a_i$$\n对于计算有理数取模的方法，请参考[模板题](https://www.luogu.com.cn/problem/P2613)。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10323","tags":["数学","洛谷原创","O2优化","期望","线性代数","微积分","洛谷比赛"],"sample_group":[["3\n1 4 4\n3 7 7\n5 10 10","0"],["5\n1 4 4\n2 5 5\n3 7 7\n4 8 8\n9 8 8","488831003"],["5\n1 1 4\n2 2 5\n3 3 7\n4 2 8\n9 3 8","884183796"],["10\n123 1 10\n234 11 14\n345 10 20\n456 6 6\n567 20 30\n678 84 90\n789 1 3\n8910 8 15\n91011 123 129\n101112 56 64","483360041"]],"created_at":"2026-03-03 11:09:25"}}