题意简述
给定N个互相独立的随机变量，第i个变量XiX_iXi 在区间[Li,Ri][L_i,R_i][Li ,Ri ]上连续均匀分布。求这N个数里第K大的数学期望E。
输出E在模998244353下的值。题目保证E写成最简分数yx\frac{y}{x}xy 时，x和模数互质，输出等价于 y⋅x−1 mod 998244353y\cdot x^{-1}\bmod 998244353y⋅x−1mod998244353。
约束：1≤N≤501\le N\le501≤N≤50，0≤Li<Ri≤1000\le L_i<R_i\le1000≤Li <Ri ≤100，所有Li,RiL_i,R_iLi ,Ri 都是整数。
核心数学知识
对于非负连续随机变量X，有期望公式：
E(X)=∫0+∞P(X≥t),dtE(X)=\int_{0}^{+\infty} P(X\ge t),dt E(X)=∫0+∞ P(X≥t),dt
本题的X就是N个随机变量的第K大。
> 含义：第K大大于等于t的概率，对t做积分，直接得到期望，不需要求复杂的概率密度函数，这是本题最关键的技巧。
设(g(t))(g(t))(g(t)) = 恰好至少有K个XiX_iXi 满足Xi≥tX_i\ge tXi ≥t的概率，那么 E=∫(g(t))dtE=\int (g(t))dtE=∫(g(t))dt。
对于单个变量XiX_iXi ：
1. 如果 t≤Lit\le L_it≤Li ：Xi≥tX_i\ge tXi ≥t一定成立，概率等于1。
2. 如果 Li<t<RiL_i<t<R_iLi <t<Ri ：概率等于 Ri−tRi−Li\frac{R_i-t}{R_i-L_i}Ri −Li Ri −t 。
3. 如果 t≥Rit\ge R_it≥Ri ：Xi≥tX_i\ge tXi ≥t不可能成立，概率等于0。
记pi(t)p_i(t)pi (t)为Xi≥tX_i\ge tXi ≥t的概率。
我们需要求：从N个里面选出至少K个，选中的都满足大于等于t，剩下的小于t的总概率。也就是动态规划：
设(dp[s])(dp[s])(dp[s])表示有s个变量满足Xi≥tX_i\ge tXi ≥t的概率。
初始(dp[0]=1)(dp[0]=1)(dp[0]=1)。逐个处理每个i：
dp′[0]=dp[0]⋅(1−pi(t))dp'[0]=dp[0]\cdot(1-p_i(t)) dp′[0]=dp[0]⋅(1−pi (t))
dp′[s]=(dp[s])⋅(1−pi(t))+dp[s−1]⋅pi(t)dp'[s]=(dp[s])\cdot(1-p_i(t))+dp[s-1]\cdot p_i(t) dp′[s]=(dp[s])⋅(1−pi (t))+dp[s−1]⋅pi (t)
处理完所有变量后，(g(t))=∑s=KN(dp[s])(g(t))=\sum_{s=K}^{N} (dp[s])(g(t))=∑s=KN (dp[s])。
值域分段
注意所有Li,RiL_i,R_iLi ,Ri 都是0~100的整数。函数pi(t)p_i(t)pi (t)的表达式只会在这些整数点发生改变。把0到100按照所有Li,RiL_i,R_iLi ,Ri 切分成若干小区间，每一段([A,B])([A,B])([A,B])内部，所有pi(t)p_i(t)pi (t)都是关于t的一次多项式，因此(g(t))(g(t))(g(t))在([A,B])([A,B])([A,B])内是一个多项式。
在每一段([A,B])([A,B])([A,B])内部，(g(t))(g(t))(g(t))是固定形式的多项式，我们直接计算定积分 ∫AB(g(t))dt\int_{A}^{B} (g(t))dt∫AB (g(t))dt，把全部区间的积分结果累加，就是总期望E。
N最多50，所以dp数组最多到50项，每一段内(g(t))最高次数最多N次。在一段区间([A,B])([A,B])([A,B])，多项式积分可以直接算解析结果。
模运算处理
全部计算在模998244353有限域完成。除法等价于乘模逆元。
1. Ri−tRi−Li\frac{R_i-t}{R_i-L_i}Ri −Li Ri −t ：分母Ri−LiR_i-L_iRi −Li ，计算它的模逆元。
2. 多项式里面所有系数全部保存为模意义下整数。
3. 定积分：例如∫tmdt\int t^m dt∫tmdt，模下除以(m+1)(m+1)(m+1)，等价乘(m+1)(m+1)(m+1)的逆元。
4. 每一段算完积分值，累加到答案。
算法步骤
1. 收集全部Li,RiL_i,R_iLi ,Ri ，排序去重，得到分割点序列0=a0<a1<a2<…<am=1000=a_0<a_1<a_2<…<a_m=1000=a0 <a1 <a2 <…<am =100。
2. 遍历每一个小区间[l,r]=[apos,apos+1][l, r]=[a_{pos},a_{pos+1}][l,r]=[apos ,apos+1 ]。
3. 在区间([l,r])([l,r])([l,r])内部：
* 对每个i，写出pi(t)p_i(t)pi (t)的表达式，它要么是常数0，常数1，要么是 ci⋅t+dic_i\cdot t+d_ici ⋅t+di 的一次式。
* 运行dp：(dp[s])维护“恰好s个变量≥t”的多项式。每加入一个i，用pi(t)p_i(t)pi (t)和1−pi(t)1-p_i(t)1−pi (t)做多项式卷积更新dp数组。
* 把dp[K],dp[K+1],…dp[N]全部相加，得到多项式(g(t))(g(t))(g(t))。
* 计算定积分∫lr(g(t))dt\int_{l}^{r} (g(t))dt∫lr (g(t))dt，模998244353，加到总答案。
4. 所有区间处理完毕，输出总答案。
复杂度分析
分割点最多2*N个，N≤50。每个区间内DP，每次转移是多项式运算，多项式最高次数N。总复杂度可以轻松通过本题时间限制。
易错点
1. 题目是第K大，不是第K小。第K大：至少K个元素≥t；如果是第K小条件完全不同。
2. 不要直接浮点数计算，全程模运算，浮点数会丢失精度。
3. 分段边界不要漏点，所有L,R都要作为分割点。
4. 多项式积分的时候，tmt^mtm积分结果是t(m+1)(m+1)\frac{t^{(m+1)}}{(m+1)}(m+1)t(m+1) ，不要忘记除以(m+1)。
5. pi(t)p_i(t)pi (t)三种情况判断：t在L左边、中间、R右边，不要写反分子。
样例简单解释
样例1输入：
只有1个变量，第1大就是它自己。期望是区间中点1。模意义下 111。
样例2输出707069751，就是分数1，模998244353下的另一种写法（等价2⋅inv(2)2\cdot inv(2)2⋅inv(2)）。
可选简化思路
因为N只有50，区间段很短，也可以把多项式全部展开，每一段用代数方法暴力展开系数，再逐项积分。
> 核心思想回顾：连续随机变量期望用 E=∫P(X≥t)dtE=\int P(X\ge t)dtE=∫P(X≥t)dt 转化，按间断点分段，每段多项式+动态规划求概率多项式，分段积分求和得到期望。全部运算在模998244353域完成。# A75084 第K大 纯文字题解
题意简述
给定N个互相独立的随机变量，第i个变量XiX_iXi 在区间[Li,Ri][L_i,R_i][Li ,Ri ]上连续均匀分布。求这N个数里第K大的数学期望E。
输出E在模998244353下的值。题目保证E写成最简分数yx\frac{y}{x}xy 时，x和模数互质，输出等价于 y⋅x−1 mod 998244353y\cdot x^{-1}\bmod 998244353y⋅x−1mod998244353。
约束：1≤N≤501\le N\le501≤N≤50，0≤Li<Ri≤1000\le L_i<R_i\le1000≤Li <Ri ≤100，所有Li,RiL_i,R_iLi ,Ri 都是整数。
核心数学知识
对于非负连续随机变量X，有期望公式：
E(X)=∫0+∞P(X≥t),dtE(X)=\int_{0}^{+\infty} P(X\ge t),dt E(X)=∫0+∞ P(X≥t),dt
本题的X就是N个随机变量的第K大。
> 含义：第K大大于等于t的概率，对t做积分，直接得到期望，不需要求复杂的概率密度函数，这是本题最关键的技巧。
设(g(t))(g(t))(g(t)) = 恰好至少有K个XiX_iXi 满足Xi≥tX_i\ge tXi ≥t的概率，那么 E=∫(g(t))dtE=\int (g(t))dtE=∫(g(t))dt。
对于单个变量XiX_iXi ：
1. 如果 t≤Lit\le L_it≤Li ：Xi≥tX_i\ge tXi ≥t一定成立，概率等于1。
2. 如果 Li<t<RiL_i<t<R_iLi <t<Ri ：概率等于 Ri−tRi−Li\frac{R_i-t}{R_i-L_i}Ri −Li Ri −t 。
3. 如果 t≥Rit\ge R_it≥Ri ：Xi≥tX_i\ge tXi ≥t不可能成立，概率等于0。
记pi(t)p_i(t)pi (t)为Xi≥tX_i\ge tXi ≥t的概率。
我们需要求：从N个里面选出至少K个，选中的都满足大于等于t，剩下的小于t的总概率。也就是动态规划：
设(dp[s])(dp[s])(dp[s])表示有s个变量满足Xi≥tX_i\ge tXi ≥t的概率。
初始(dp[0]=1)(dp[0]=1)(dp[0]=1)。逐个处理每个i：
dp′[0]=dp[0]⋅(1−pi(t))dp'[0]=dp[0]\cdot(1-p_i(t)) dp′[0]=dp[0]⋅(1−pi (t))
dp′[s]=(dp[s])⋅(1−pi(t))+dp[s−1]⋅pi(t)dp'[s]=(dp[s])\cdot(1-p_i(t))+dp[s-1]\cdot p_i(t) dp′[s]=(dp[s])⋅(1−pi (t))+dp[s−1]⋅pi (t)
处理完所有变量后，(g(t))=∑s=KN(dp[s])(g(t))=\sum_{s=K}^{N} (dp[s])(g(t))=∑s=KN (dp[s])。
值域分段
注意所有Li,RiL_i,R_iLi ,Ri 都是0~100的整数。函数pi(t)p_i(t)pi (t)的表达式只会在这些整数点发生改变。把0到100按照所有Li,RiL_i,R_iLi ,Ri 切分成若干小区间，每一段([A,B])([A,B])([A,B])内部，所有pi(t)p_i(t)pi (t)都是关于t的一次多项式，因此(g(t))(g(t))(g(t))在([A,B])([A,B])([A,B])内是一个多项式。
在每一段([A,B])([A,B])([A,B])内部，(g(t))(g(t))(g(t))是固定形式的多项式，我们直接计算定积分 ∫AB(g(t))dt\int_{A}^{B} (g(t))dt∫AB (g(t))dt，把全部区间的积分结果累加，就是总期望E。
N最多50，所以dp数组最多到50项，每一段内(g(t))最高次数最多N次。在一段区间([A,B])([A,B])([A,B])，多项式积分可以直接算解析结果。
模运算处理
全部计算在模998244353有限域完成。除法等价于乘模逆元。
1. Ri−tRi−Li\frac{R_i-t}{R_i-L_i}Ri −Li Ri −t ：分母Ri−LiR_i-L_iRi −Li ，计算它的模逆元。
2. 多项式里面所有系数全部保存为模意义下整数。
3. 定积分：例如∫tmdt\int t^m dt∫tmdt，模下除以(m+1)(m+1)(m+1)，等价乘(m+1)(m+1)(m+1)的逆元。
4. 每一段算完积分值，累加到答案。
算法步骤
1. 收集全部Li,RiL_i,R_iLi ,Ri ，排序去重，得到分割点序列0=a0<a1<a2<…<am=1000=a_0<a_1<a_2<…<a_m=1000=a0 <a1 <a2 <…<am =100。
2. 遍历每一个小区间[l,r]=[apos,apos+1][l, r]=[a_{pos},a_{pos+1}][l,r]=[apos ,apos+1 ]。
3. 在区间([l,r])([l,r])([l,r])内部：
* 对每个i，写出pi(t)p_i(t)pi (t)的表达式，它要么是常数0，常数1，要么是 ci⋅t+dic_i\cdot t+d_ici ⋅t+di 的一次式。
* 运行dp：(dp[s])维护“恰好s个变量≥t”的多项式。每加入一个i，用pi(t)p_i(t)pi (t)和1−pi(t)1-p_i(t)1−pi (t)做多项式卷积更新dp数组。
* 把dp[K],dp[K+1],…dp[N]全部相加，得到多项式(g(t))(g(t))(g(t))。
* 计算定积分∫lr(g(t))dt\int_{l}^{r} (g(t))dt∫lr (g(t))dt，模998244353，加到总答案。
4. 所有区间处理完毕，输出总答案。
复杂度分析
分割点最多2*N个，N≤50。每个区间内DP，每次转移是多项式运算，多项式最高次数N。总复杂度可以轻松通过本题时间限制。
易错点
1. 题目是第K大，不是第K小。第K大：至少K个元素≥t；如果是第K小条件完全不同。
2. 不要直接浮点数计算，全程模运算，浮点数会丢失精度。
3. 分段边界不要漏点，所有L,R都要作为分割点。
4. 多项式积分的时候，tmt^mtm积分结果是t(m+1)(m+1)\frac{t^{(m+1)}}{(m+1)}(m+1)t(m+1) ，不要忘记除以(m+1)。
5. pi(t)p_i(t)pi (t)三种情况判断：t在L左边、中间、R右边，不要写反分子。
样例简单解释
样例1输入：
只有1个变量，第1大就是它自己。期望是区间中点1。模意义下 111。
样例2输出707069751，就是分数1，模998244353下的另一种写法（等价2⋅inv(2)2\cdot inv(2)2⋅inv(2)）。
可选简化思路
因为N只有50，区间段很短，也可以把多项式全部展开，每一段用代数方法暴力展开系数，再逐项积分。
> 核心思想回顾：连续随机变量期望用 E=∫P(X≥t)dtE=\int P(X\ge t)dtE=∫P(X≥t)dt 转化，按间断点分段，每段多项式+动态规划求概率多项式，分段积分求和得到期望。全部运算在模998244353域完成。
最后，来看代码：
