102267: [AtCoder]ABC226 H - Random Kth Max
Description
Score : $600$ points
Problem Statement
We have $N$ continuous random variables $X_1,X_2,\dots,X_N$. $X_i$ has a continuous uniform distribution over the interval $\lbrack L_i, R_i \rbrack$.
Let $E$ be the expected value of the $K$-th greatest value among the $N$ random variables. Print $E \bmod {998244353}$ as specified in Notes.
Notes
In this problem, we can prove that $E$ is always a rational number. Additionally, the Constraints of this problem guarantee that, when $E$ is represented as an irreducible fraction $\frac{y}{x}$, $x$ is indivisible by $998244353$.
Here, there uniquely exists an integer $z$ between $0$ and $998244352$ such that $xz \equiv y \pmod{998244353}$. Print this $z$ as the value $E \bmod {998244353}$.
Constraints
- $1 \leq N \leq 50$
- $1 \leq K \leq N$
- $0 \leq L_i \lt R_i \leq 100$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $K$ $L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_N$ $R_N$
Output
Print $E \bmod {998244353}$.
Sample Input 1
1 1 0 2
Sample Output 1
1
The answer is the expected value of the random variable with a continuous uniform distribution over the interval $\lbrack 0, 2 \rbrack$. Thus, we should print $1$.
Sample Input 2
2 2 0 2 1 3
Sample Output 2
707089751
The answer represented as a rational number is $\frac{23}{24}$. We have $707089751 \times 24 \equiv 23 \pmod{998244353}$, so we should print $707089751$.
Sample Input 3
10 5 35 48 44 64 47 59 39 97 36 37 4 91 38 82 20 84 38 50 39 69
Sample Output 3
810056397
Input
题意翻译
有 $n$ 个连续随机变量 $X_1, X_2, \dots, X_n$,$X_i$ 在 $[l_i, r_i]$ 上连续均匀分布。令 $E$ 为这 $n$ 个变量的第 $k$ 大值的期望,请求得 $E$ 在模 $998244353$ 意义下的值。 在本题的限制下,我们可以证明 $E$ 总能被表示为 $p / q$ 的形式,其中 $p, q$ 为 $< 998244353$ 的非负整数,且 $q$ 不为 $0$。你需要输出的即为一个 $< 998244353$ 的非负整数 $r$,满足 $qr \equiv p \pmod{998244353}$。 $1\le n\le 50,\ 1\le k\le n, \ 0\le l_i < r_i \le 100$,任意 $l_i, r_i$ 为整数。Output
问题描述
我们有$N$个连续随机变量$X_1,X_2,\dots,X_N$。$X_i$在区间$\lbrack L_i, R_i \rbrack$上具有连续均匀分布。
令$E$为这$N$个随机变量中第$K$大的值的期望值。按照Notes中的指定,打印$E \bmod {998244353}$。
注意
在这个问题中,我们可以证明$E$总是有理数。此外,本问题的约束条件保证,当$E$表示为不可约分数$\frac{y}{x}$时,$x$不能被$998244353$整除。
在这里,存在一个介于$0$和$998244352$之间的整数$z$,使得$xz \equiv y \pmod{998244353}$。打印这个$z$作为$E \bmod {998244353}$的值。
约束条件
- $1 \leq N \leq 50$
- $1 \leq K \leq N$
- $0 \leq L_i \lt R_i \leq 100$
- 输入中的所有值都是整数。
输入
输入通过标准输入以以下格式给出:
$N$ $K$ $L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_N$ $R_N$
输出
打印$E \bmod {998244353}$。
样例输入1
1 1 0 2
样例输出1
1
答案是区间$\lbrack 0, 2 \rbrack$上具有连续均匀分布的随机变量的期望值。因此,我们应该打印$1$。
样例输入2
2 2 0 2 1 3
样例输出2
707089751
答案表示为有理数为$\frac{23}{24}$。我们有$707089751 \times 24 \equiv 23 \pmod{998244353}$,所以我们应该打印$707089751$。
样例输入3
10 5 35 48 44 64 47 59 39 97 36 37 4 91 38 82 20 84 38 50 39 69
样例输出3
810056397