2125D.md (1532B)
1 Source: https://codeforces.com/problemset/problem/2125/D 2 3 D. Segments Covering 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 There is a linear strip divided into $m$ cells, numbered from $1$ to $m$ from left to right. 22 23 You are given $n$ segments. Each segment is defined by four numbers: $l$, $r$, $p$ and $q$ — the segment covers cells from $l$ to $r$ inclusively and exists with probability $\frac{p}{q}$ (independently). 24 25 Your task is to calculate the probability that each cell is covered by exactly one segment. 26 27 Input 28 29 The first line contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$). 30 31 Then $n$ lines follow. The $i$-th of them contains four integers $l_i$, $r_i$, $p_i$ and $q_i$ ($1 \le l_i \le r_i \le m$; $1 \le p_i \lt q_i \lt 998244353$). 32 33 Output 34 35 Print a single integer — the probability that each cell is covered by exactly one segment, taken modulo $998244353$. 36 37 Formally, the probability can be expressed as an irreducible fraction $\frac{x}{y}$. You have to print the value of $x \cdot y^{-1} \bmod 998244353$, where $y^{-1}$ is an integer such that $y \cdot y^{-1} \bmod 998244353 = 1$. 38 39 Examples 40 41 Input 42 43 ``` 44 3 3 45 46 1 2 1 3 47 48 3 3 1 2 49 50 1 3 2 3 51 ``` 52 53 Output 54 55 ``` 56 610038216 57 ``` 58 59 Input 60 61 ``` 62 2 3 63 64 1 2 1 2 65 66 2 3 1 2 67 ``` 68 69 Output 70 71 ``` 72 0 73 ``` 74 75 Input 76 77 ``` 78 8 5 79 80 1 3 1 2 81 82 1 5 1 6 83 84 1 4 4 5 85 86 5 5 1 7 87 88 4 5 1 2 89 90 4 5 2 5 91 92 3 3 2 7 93 94 1 2 1 3 95 ``` 96 97 Output 98 99 ``` 100 94391813 101 ``` 102 103 Note 104 105 In the first example, the probability is equal to $\frac{5}{18}$.