Random Kth Max

AtCoder

IDabc226_h

Time2000ms

Memory256MB

Difficulty—

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. ## 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$ [samples] ## 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}$.

Samples

Input #1

1 1
0 2

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$.

Input #2

2 2
0 2
1 3

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$.

Input #3

Output #3

810056397

API Response (JSON)

{
  "problem": {
    "name": "Random Kth Max",
    "description": {
      "content": "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 gr",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc226_h"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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$.  \nLet $E$ be the expected value of the $K$\\-th gr...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments