A75084 第K大 题解

题意简述

给定N个互相独立的随机变量，第i个变量$X_i$在区间$[L_i,R_i]$上连续均匀分布。求这N个数里第K大的数学期望E。
输出E在模998244353下的值。题目保证E写成最简分数$\frac{y}{x}$时，x和模数互质，输出等价于 $y\cdot x^{-1}\bmod 998244353$。

约束：$1\le N\le50$，$0\le L_i<R_i\le100$，所有$L_i,R_i$都是整数。

核心数学知识

对于非负连续随机变量X，有期望公式：

$$E(X)=\int_{0}^{+\infty} P(X\ge t),dt$$

本题的X就是N个随机变量的第K大。

含义：第K大大于等于t的概率，对t做积分，直接得到期望，不需要求复杂的概率密度函数，这是本题最关键的技巧。

设$(g(t))$ = 恰好至少有K个$X_i$满足$X_i\ge t$的概率，那么 $E=\int (g(t))dt$。

对于单个变量$X_i$：

1. 如果 $t\le L_i$：$X_i\ge t$一定成立，概率等于1。
2. 如果 $L_i<t<R_i$：概率等于 $\frac{R_i-t}{R_i-L_i}$。
3. 如果 $t\ge R_i$：$X_i\ge t$不可能成立，概率等于0。

记$p_i(t)$为$X_i\ge t$的概率。
我们需要求：从N个里面选出至少K个，选中的都满足大于等于t，剩下的小于t的总概率。也就是动态规划：
设$(dp[s])$表示有s个变量满足$X_i\ge t$的概率。
初始$(dp[0]=1)$。逐个处理每个i：

$$dp'[0]=dp[0]\cdot(1-p_i(t))$$

$$dp'[s]=(dp[s])\cdot(1-p_i(t))+dp[s-1]\cdot p_i(t)$$

处理完所有变量后，$(g(t))=\sum_{s=K}^{N} (dp[s])$。

值域分段

注意所有$L_i,R_i$都是0~100的整数。函数$p_i(t)$的表达式只会在这些整数点发生改变。把0到100按照所有$L_i,R_i$切分成若干小区间，每一段$([A,B])$内部，所有$p_i(t)$都是关于t的一次多项式，因此$(g(t))$在$([A,B])$内是一个多项式。
在每一段$([A,B])$内部，$(g(t))$是固定形式的多项式，我们直接计算定积分 $\int_{A}^{B} (g(t))dt$，把全部区间的积分结果累加，就是总期望E。

N最多50，所以dp数组最多到50项，每一段内(g(t))最高次数最多N次。在一段区间$([A,B])$，多项式积分可以直接算解析结果。

模运算处理

全部计算在模998244353有限域完成。除法等价于乘模逆元。

1. $\frac{R_i-t}{R_i-L_i}$：分母$R_i-L_i$，计算它的模逆元。
2. 多项式里面所有系数全部保存为模意义下整数。
3. 定积分：例如$\int t^m dt$，模下除以$(m+1)$，等价乘$(m+1)$的逆元。
4. 每一段算完积分值，累加到答案。

算法步骤

1. 收集全部$L_i,R_i$，排序去重，得到分割点序列$0=a_0<a_1<a_2<…<a_m=100$。
2. 遍历每一个小区间$[l, r]=[a_{pos},a_{pos+1}]$。
3. 在区间$([l,r])$内部：
   • 对每个i，写出$p_i(t)$的表达式，它要么是常数0，常数1，要么是 $c_i\cdot t+d_i$ 的一次式。
   • 运行dp：(dp[s])维护“恰好s个变量≥t”的多项式。每加入一个i，用$p_i(t)$和$1-p_i(t)$做多项式卷积更新dp数组。
   • 把dp[K],dp[K+1],…dp[N]全部相加，得到多项式$(g(t))$。
   • 计算定积分$\int_{l}^{r} (g(t))dt$，模998244353，加到总答案。
4. 所有区间处理完毕，输出总答案。

复杂度分析

分割点最多2*N个，N≤50。每个区间内DP，每次转移是多项式运算，多项式最高次数N。总复杂度可以轻松通过本题时间限制。

易错点

1. 题目是第K大，不是第K小。第K大：至少K个元素≥t；如果是第K小条件完全不同。
2. 不要直接浮点数计算，全程模运算，浮点数会丢失精度。
3. 分段边界不要漏点，所有L,R都要作为分割点。
4. 多项式积分的时候，$t^m$积分结果是$\frac{t^{(m+1)}}{(m+1)}$，不要忘记除以(m+1)。
5. $p_i(t)$三种情况判断：t在L左边、中间、R右边，不要写反分子。

样例简单解释

样例1输入：

1 1
0 2

只有1个变量，第1大就是它自己。期望是区间中点1。模意义下 $1$。
样例2输出707069751，就是分数1，模998244353下的另一种写法（等价$2\cdot inv(2)$）。

可选简化思路

因为N只有50，区间段很短，也可以把多项式全部展开，每一段用代数方法暴力展开系数，再逐项积分。

核心思想回顾：连续随机变量期望用 $E=\int P(X\ge t)dt$ 转化，按间断点分段，每段多项式+动态规划求概率多项式，分段积分求和得到期望。全部运算在模998244353域完成。# A75084 第K大 纯文字题解

题意简述

给定N个互相独立的随机变量，第i个变量$X_i$在区间$[L_i,R_i]$上连续均匀分布。求这N个数里第K大的数学期望E。
输出E在模998244353下的值。题目保证E写成最简分数$\frac{y}{x}$时，x和模数互质，输出等价于 $y\cdot x^{-1}\bmod 998244353$。

约束：$1\le N\le50$，$0\le L_i<R_i\le100$，所有$L_i,R_i$都是整数。

核心数学知识

对于非负连续随机变量X，有期望公式：

$$E(X)=\int_{0}^{+\infty} P(X\ge t),dt$$

本题的X就是N个随机变量的第K大。

含义：第K大大于等于t的概率，对t做积分，直接得到期望，不需要求复杂的概率密度函数，这是本题最关键的技巧。

设$(g(t))$ = 恰好至少有K个$X_i$满足$X_i\ge t$的概率，那么 $E=\int (g(t))dt$。

对于单个变量$X_i$：

1. 如果 $t\le L_i$：$X_i\ge t$一定成立，概率等于1。
2. 如果 $L_i<t<R_i$：概率等于 $\frac{R_i-t}{R_i-L_i}$。
3. 如果 $t\ge R_i$：$X_i\ge t$不可能成立，概率等于0。

记$p_i(t)$为$X_i\ge t$的概率。
我们需要求：从N个里面选出至少K个，选中的都满足大于等于t，剩下的小于t的总概率。也就是动态规划：
设$(dp[s])$表示有s个变量满足$X_i\ge t$的概率。
初始$(dp[0]=1)$。逐个处理每个i：

$$dp'[0]=dp[0]\cdot(1-p_i(t))$$

$$dp'[s]=(dp[s])\cdot(1-p_i(t))+dp[s-1]\cdot p_i(t)$$

处理完所有变量后，$(g(t))=\sum_{s=K}^{N} (dp[s])$。

值域分段

注意所有$L_i,R_i$都是0~100的整数。函数$p_i(t)$的表达式只会在这些整数点发生改变。把0到100按照所有$L_i,R_i$切分成若干小区间，每一段$([A,B])$内部，所有$p_i(t)$都是关于t的一次多项式，因此$(g(t))$在$([A,B])$内是一个多项式。
在每一段$([A,B])$内部，$(g(t))$是固定形式的多项式，我们直接计算定积分 $\int_{A}^{B} (g(t))dt$，把全部区间的积分结果累加，就是总期望E。

N最多50，所以dp数组最多到50项，每一段内(g(t))最高次数最多N次。在一段区间$([A,B])$，多项式积分可以直接算解析结果。

模运算处理

全部计算在模998244353有限域完成。除法等价于乘模逆元。

1. $\frac{R_i-t}{R_i-L_i}$：分母$R_i-L_i$，计算它的模逆元。
2. 多项式里面所有系数全部保存为模意义下整数。
3. 定积分：例如$\int t^m dt$，模下除以$(m+1)$，等价乘$(m+1)$的逆元。
4. 每一段算完积分值，累加到答案。

算法步骤

1. 收集全部$L_i,R_i$，排序去重，得到分割点序列$0=a_0<a_1<a_2<…<a_m=100$。
2. 遍历每一个小区间$[l, r]=[a_{pos},a_{pos+1}]$。
3. 在区间$([l,r])$内部：
   • 对每个i，写出$p_i(t)$的表达式，它要么是常数0，常数1，要么是 $c_i\cdot t+d_i$ 的一次式。
   • 运行dp：(dp[s])维护“恰好s个变量≥t”的多项式。每加入一个i，用$p_i(t)$和$1-p_i(t)$做多项式卷积更新dp数组。
   • 把dp[K],dp[K+1],…dp[N]全部相加，得到多项式$(g(t))$。
   • 计算定积分$\int_{l}^{r} (g(t))dt$，模998244353，加到总答案。
4. 所有区间处理完毕，输出总答案。

复杂度分析

分割点最多2*N个，N≤50。每个区间内DP，每次转移是多项式运算，多项式最高次数N。总复杂度可以轻松通过本题时间限制。

易错点

1. 题目是第K大，不是第K小。第K大：至少K个元素≥t；如果是第K小条件完全不同。
2. 不要直接浮点数计算，全程模运算，浮点数会丢失精度。
3. 分段边界不要漏点，所有L,R都要作为分割点。
4. 多项式积分的时候，$t^m$积分结果是$\frac{t^{(m+1)}}{(m+1)}$，不要忘记除以(m+1)。
5. $p_i(t)$三种情况判断：t在L左边、中间、R右边，不要写反分子。

样例简单解释

样例1输入：

1 1
0 2

只有1个变量，第1大就是它自己。期望是区间中点1。模意义下 $1$。
样例2输出707069751，就是分数1，模998244353下的另一种写法（等价$2\cdot inv(2)$）。

可选简化思路

因为N只有50，区间段很短，也可以把多项式全部展开，每一段用代数方法暴力展开系数，再逐项积分。

核心思想回顾：连续随机变量期望用 $E=\int P(X\ge t)dt$ 转化，按间断点分段，每段多项式+动态规划求概率多项式，分段积分求和得到期望。全部运算在模998244353域完成。

最后，来看代码：

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;
const int MAXN = 55;

long long pow_mod(long long a, long long b) {
long long res = 1;
a %= MOD;
while (b) {
if (b & 1) res = res * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return res;
}

int main() {
int N, K;
cin >> N >> K;
vector<int> L(N), R(N);
set<int> points;
points.insert(0);
points.insert(100);
for (int i = 0; i < N; i++) {
cin >> L[i] >> R[i];
points.insert(L[i]);
points.insert(R[i]);
}
vector<int> breaks(points.begin(), points.end());
sort(breaks.begin(), breaks.end());

vector<long long> inv(MAXN+1);
for (int i=1; i<=MAXN; i++) {
inv[i] = pow_mod(i, MOD-2);
}

long long ans = 0;
for (int i=0; i<breaks.size()-1; i++) {
int l = breaks[i], r = breaks[i+1];
vector<vector<long long>> dp(N+1, vector<long long>(MAXN, 0));
dp[0][0] = 1;

for (int idx=0; idx<N; idx++) {
    vector<vector<long long>> ndp(N+1, vector<long long>(MAXN, 0));
    int L_i = L[idx], R_i = R[idx];
    int type;
    if (r <= L_i) type = 1;
    else if (l >= R_i) type = 0;
    else type = 2;
    
    long long a, b, c, d;
    if (type == 2) {
        long long len = R_i - L_i;
        long long inv_len = pow_mod(len, MOD-2);
        a = (MOD - inv_len) % MOD;
        b = (long long)R_i * inv_len % MOD;
        c = inv_len;
        d = (-L_i * inv_len) % MOD;
        if (d < 0) d += MOD;
    }
    
    for (int j=0; j<=N; j++) {
        for (int k=0; k<MAXN; k++) {
            if (dp[j][k] == 0) continue;
            if (type == 0) {
                ndp[j][k] = (ndp[j][k] + dp[j][k]) % MOD;
            } else if (type == 1) {
                if (j+1 <= N) {
                    ndp[j+1][k] = (ndp[j+1][k] + dp[j][k]) % MOD;
                }
            } else {
                ndp[j][k] = (ndp[j][k] + dp[j][k] * d) % MOD;
                if (k+1 < MAXN) {
                    ndp[j][k+1] = (ndp[j][k+1] + dp[j][k] * c) % MOD;
                }
                if (j+1 <= N) {
                    ndp[j+1][k] = (ndp[j+1][k] + dp[j][k] * b) % MOD;
                    if (k+1 < MAXN) {
                        ndp[j+1][k+1] = (ndp[j+1][k+1] + dp[j][k] * a) % MOD;
                    }
                }
            }
        }
    }
    dp = ndp;
}

vector<long long> F(MAXN, 0);
for (int j=K; j<=N; j++) {
    for (int k=0; k<MAXN; k++) {
        F[k] = (F[k] + dp[j][k]) % MOD;
    }
}

long long I = 0;
for (int k=0; k<MAXN; k++) {
    if (F[k] == 0) continue;
    long long term1 = pow_mod(r, k+1);
    long long term2 = pow_mod(l, k+1);
    long long diff = (term1 - term2 + MOD) % MOD;
    I = (I + F[k] * diff % MOD * inv[k+1]) % MOD;
}
ans = (ans + I) % MOD;
}
cout << ans << endl;
return 0;
}