Random intervals
本题没有可用的提交语言。
Description
Dani has two integers $n$ and $m$ and a button which does the following when pressed:
- Generates $n$ random intervals of the form $(l, r)$ where $1 \leq l \leq r \leq m$.
Dani has pressed the button two times, but he has only given you the $n$ randomly generated intervals from the first press of the button. Please, help Dani to know the probability of not having any pair of intersecting intervals.
A pair of intervals $(i, j)$ don't intersect if and only if $r_{i} \leq l_{j}$ or $r_{j} \leq l_{i}$. Note that it's not guaranteed that after the first button press no pair of intervals intersect. For more information check the notes section below the samples.
It can be proven that the probability can be represented as an simple fraction $P/Q$ where $Q$ is coprime to $998244353$ . Output the value of $P \cdot Q^{-1}$ modulo $998244353$ .
Each test contains multiple test cases. The first line contains the number of test cases $t$ $(1 \leq t \leq 69)$. The description of the test cases follows.
The first line consists in two integers $n, m$ $(1 \leq n \leq 269 ; 1 \leq m \leq 6.9 \cdot 10^{6})$ — the number of generated intervals after pressing the button and the upper bound of the intervals endpoints, respectively.
Then follows $n$ lines, each one consisting in two integers $l_{i}, r_{i}$ $(1 \leq l_{i} \leq r_{i} \leq m)$ — the endpoints of the generated intervals.
It is guaranteed that the sum of $n$ over all test cases does not exceed $269$.
For each testcase, output a single integer — the probability of not having any pair of intersecting intervals modulo $998244353$.
Input
Each test contains multiple test cases. The first line contains the number of test cases $t$ $(1 \leq t \leq 69)$. The description of the test cases follows.
The first line consists in two integers $n, m$ $(1 \leq n \leq 269 ; 1 \leq m \leq 6.9 \cdot 10^{6})$ — the number of generated intervals after pressing the button and the upper bound of the intervals endpoints, respectively.
Then follows $n$ lines, each one consisting in two integers $l_{i}, r_{i}$ $(1 \leq l_{i} \leq r_{i} \leq m)$ — the endpoints of the generated intervals.
It is guaranteed that the sum of $n$ over all test cases does not exceed $269$.
Output
For each testcase, output a single integer — the probability of not having any pair of intersecting intervals modulo $998244353$.
8
1 3
2 2
3 4
3 3
1 3
3 3
2 4
1 1
3 4
4 10
5 7
2 2
3 4
9 9
2 15
1 3
2 5
2 69
8 11
9 10
1 10
1 1
2 11
3 3
3 3
831870295
726721889
259543532
10510086
0
0
1
501184665
Note
In the first test case, there are $6$ possible distributions, but only $5$ are valid. This is because if the generated interval was $(1, 3)$ the intervals $(2, 2)$ and $(1, 3)$ would intersect.
In the fourth test case, there are $100$ possible distributions, but only $22$ are valid.
In the fifth testcase, the answer is $0$ because some of the intervals generated after the first press of the button intersect.
—
Problem idea: danx
Problem preparation: danx
Ocurrences: Advanced 6