| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 (추가 시간 없음) | 1024 MB | 30 | 16 | 16 | 61.538% |
Iris works for the host of the 2022 ICPC Taoyuan Regional Contest. Due to COVID-19, the ICPC regional contests in Taiwan could not invite any leader to the opening ceremony in the past few years. The host of the 2022 ICPC Taoyuan Regional Contest is eager to invite leaders in Taoyuan City to attend the opening ceremony.
There are $n$ leaders numbered from $1$ to $n$ in Taoyuan City, and Iris’s task is to invite some leaders to attend the ceremony. Leader $i$ is available from time slot $ℓ_i$ to time slot $r_i$. If Iris wants to invite $k$ leaders $a_1, a_2, \dots ,a_k$, then all of them must have a common available time slot. It means that Iris has to find a time slot $x$ such that $ℓ_{a_i} ≤ x ≤ r_{a_i}$ for $1 ≤ i ≤ k$.
Iris is curious about the number of combinations of $k$ leaders available at the same time? You need to give the answers for all $k$ between $1$ and $n$. The combinations may be extremely numerous, please output the number of combinations modulo $998244353$.
The first line of input contains one integer $n$, the number of leaders. The following $n$ lines indicate the leaders’ available time slots. The $i$-th line of these $n$ lines contains two numbers $ℓ_i$ and $r_i$. The $i$-th leader is available at time $ℓ_i$ to $r_i$.
Print $n$ numbers. The $k$-th number is the number of combinations of $k$ leaders having a common available time slot. Please modulo the answer with $998244353$.
3 1 2 2 3 3 4
3 2 0
ICPC > Regionals > Asia Pacific > Taiwan > Taiwan Online Programming Contest > TOPC 2022 I번