Background

The statement and sample attachments are from QOJ。

When submitting to Luogu, you do not need to include the header #include "segment.h"。Just copy

void init(int c, int t);
std::vector<int> segment(int n, int m, int k, std::vector<int> l, std::vector<int> r);

to the beginning of your program, and compile with a C++17 or higher compiler.

Problem Description

Xiao $L$ has $n$ segments contained in $[1,m]$。The $i$-th ($0\le i<n$) segment is $[l_i,r_i]$ ($1\le l_i\le r_i\le m$)。

Xiao $L$ thinks that overly complicated segment intersection relationships are not elegant。For every segment set $S\subseteq\{0,1,\ldots,n-1\}$, Xiao $L$ defines $S$ to be elegant if and only if it satisfies the following:

• Construct a graph whose vertex set corresponds to $S$。There is an edge between vertex $u$ and vertex $v$ if and only if segment $u$ and segment $v$ intersect, i.e. there exists $x\in[1,m]$ such that $l_u\le x\le r_u$ and $l_v\le x\le r_v$。We say $S$ is elegant if and only if the constructed graph is exactly a tree.

Xiao $L$ wants to know how many segment sets are elegant, so he is given a positive integer $k$ ($k\le n$)。You need to compute, for each $s=1,2,\ldots,k$, how many elegant sets of size $s$ there are.

Since the answer may be large, you only need to output the result modulo $998,244,353$。

【How to use the test program】

Contestants do not need to, and should not, implement the main function。

Contestants must ensure that the submitted source file includes the header segment.h, i.e. add the following code at the beginning of the program:

#include "segment.h"

Contestants need to implement the following two functions in the submitted source file segment.cpp:

void init(int c, int t);

• $c,t$ denote the test point ID and the number of testdata groups, respectively。$c=0$ means this test point is the sample.
• For each test point, this function will be called by the judge exactly once when the program starts.

std::vector<int> segment(int n, int m, int k, std::vector<int> l, std::vector<int> r);

• $n,m,k$ denote the number of segments, the upper bound of the coordinate range, and the maximum set size to compute, respectively.
• $l,r$ denote the left endpoints and right endpoints of each segment, respectively.
• This function needs to return a sequence $a$ of length exactly $k+1$, where $a_0=0$, and $a_s$ ($1\le s\le k$) is the number of elegant sets of size $s$ modulo $998,244,353$.
• For each test point, this function will be called by the judge exactly $t$ times.

template_segment.cpp in this problem directory is the provided sample code. Contestants may refer to it and implement their own code.

Constraints

Let $K$ be the sum of $k$ over all testdata within a single test point。For all testdata, we have:

• $1\le t\le20$；
• $1\le n\le3000$，$1\le m\le10^3$，$1\le k\le n$，$K\le200$；
• For all $0\le i<n$, we have $1\le l_i\le r_i\le m$。

::cute-table{tuack} | Test Point ID | $n\le$ | $m\le$ | $K\le$ | $k\le$ | Special Property | |:-:|:-:|:-:|:-:|:-:|:-:| | $1\sim3$ | $20$ | $10^2$ | $20$ | $20$ | None | | $4,5$ | $3000$ | $10^3$ | $200$ | $2$ | ^ | | $6\sim8$ | ^ | ^ | ^ | $3$ | ^ | | $9,10$ | $500$ | ^ | ^ | $200$ | $A$ | | $11\sim15$ | $3000$ | ^ | ^ | ^ | $B$ | | $16\sim18$ | $200$ | $500$ | $50$ | $50$ | $C$ | | $19\sim21$ | $500$ | $10^3$ | $200$ | $200$ | ^ | | $22,23$ | $10^3$ | $10^2$ | $30$ | $30$ | None | | $24,25$ | $3000$ | $10^3$ | $200$ | $200$ | ^ |

• Special property $A$: For all $0\le i,j<n$ with $i\ne j$, segment $i$ does not contain segment $j$, i.e. $l_i>l_j$ or $r_i<r_j$.
• Special property $B$: For all $0\le i<j<n$, either segment $i$ contains segment $j$, or segment $i$ and segment $j$ do not intersect, i.e. $l_i\le l_j\le r_j\le r_i$, $r_i<l_j$, or $l_i>r_j$.
• Special property $C$: All $2n$ endpoints of the $n$ segments are pairwise distinct, i.e. $l_0,l_1,\ldots,l_{n-1},r_0,r_1,\ldots,r_{n-1}$ are all different.

Input Format

You can compile in this problem directory using the following command to obtain an executable file:

g++ grader.cpp segment.cpp -o segment -O2 -std=c++14 -static

For the compiled executable segment:

• The executable will read input from standard input in the following format:
  • The first line contains two non-negative integers $c,t$.
  • Then follow the testdata groups. For each group of testdata:
    • The first line contains three positive integers $n,m,k$.
    • Line $i+2$ ($0\le i<n$) contains two positive integers $l_i,r_i$.
• The executable will output to standard output in the following format:
  • For each group of testdata, output one line with $k$ non-negative integers $a_1,a_2,\ldots,a_k$.

0 3
3 3 3
1 2
2 3
1 3
4 5 4
1 2
2 3
3 4
4 5
4 2 3
1 2
1 2
1 2
1 1

3 3 0
4 3 2 1
4 6 0

Hint

【Sample $1$ Explanation】

For the first group of testdata:

• For size $1$, the sets $\{0\},\{1\},\{2\}$ are all elegant.
• For size $2$, the sets $\{0,1\},\{1,2\},\{0,2\}$ are all elegant.
• For size $3$, the set $\{0,1,2\}$ constructs a 3-cycle, so it is not elegant.

Therefore the answers are $3,3,0$.

For the second group of testdata:

• For size $1$, all $4$ sets are elegant.
• For size $2$, $\{0,1\},\{1,2\},\{2,3\}$ are elegant.
• For size $3$, $\{0,1,2\},\{1,2,3\}$ are elegant.
• The size $4$ set $\{0,1,2,3\}$ is elegant.

Therefore the answers are $4,3,2,1$.

【Sample $2$】

See segment/segment2.in and segment/segment2.ans in the contestant directory.

This sample satisfies the constraints of test points $6\sim8$.

【Sample $3$】

See segment/segment3.in and segment/segment3.ans in the contestant directory.

This sample satisfies the constraints of test points $9,10$.

【Sample $4$】

See segment/segment4.in and segment/segment4.ans in the contestant directory.

This sample satisfies the constraints of test points $11\sim15$.

【Sample $5$】

See segment/segment5.in and segment/segment5.ans in the contestant directory.

This sample satisfies the constraints of test points $16\sim18$.

【Sample $6$】

See segment/segment6.in and segment/segment6.ans in the contestant directory.

This sample satisfies the constraints of test points $22,23$.

【Sample $7$】

See segment/segment7.in and segment/segment7.ans in the contestant directory.

This sample satisfies the constraints of test points $24,25$.

Translated by ChatGPT 5