题目描述

小 $L$ 有 $n$ 条包含于 $[1,m]$ 的线段，其中第 $i$（$0\le i<n$）条线段为 $[l_i,r_i]$（$1\le l_i\le r_i\le m$）。

小 $L$ 认为过于复杂的线段相交关系不够优美。对于每一个线段集合 $S\subseteq\{0,1,\ldots,n-1\}$，小 $L$ 定义 $S$ 是 优美 的，当且仅当满足如下要求：

• 构造一个顶点集合与 $S$ 对应的图。顶点 $u$ 与顶点 $v$ 之间存在一条边，当且仅当线段 $u$ 与线段 $v$ 相交，即存在 $x\in[1,m]$，满足 $l_u\le x\le r_u$ 且 $l_v\le x\le r_v$。称 $S$ 是 优美 的，当且仅当构造出的图恰好为一棵树。

小 $L$ 想知道有多少线段集合是优美的，因此他给定了一个正整数 $k$（$k\le n$）。你需要计算，对于每个 $s=1,2,\ldots,k$，有多少个大小为 $s$ 的集合是优美的。

由于答案可能较大，只需求出答案对 $998244353$ 取模后的结果。

【测试程序方式】

选手不需要，也不应该实现 main 函数。

选手需要确保提交的程序源文件包含头文件 segment.h，即在程序开头加入以下代码：

#include "segment.h"

选手需要在提交的程序源文件 segment.cpp 中实现以下两个函数：

void init(int c, int t);

• $c,t$ 分别表示测试点编号与测试数据组数。$c=0$ 表示该测试点为样例。
• 对于每个测试点，该函数会在程序开始运行时被评测程序调用恰好一次。

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

• $n,m,k$ 分别表示线段的数量、坐标范围上限及需要计算的集合大小上限。
• $l,r$ 分别表示每条线段的左端点与右端点。
• 该函数需要返回一个长度 恰好 为 $k+1$ 的序列 $a$，其中 $a_0=0$，$a_s$（$1\le s\le k$）表示大小为 $s$ 的优美集合数量对 $998244353$ 取模后的结果。
• 对于每个测试点，该函数会被评测程序调用恰好 $t$ 次。

本试题目录下的 template_segment.cpp 是提供的示例代码，选手可参考并实现自己的代码。

输入格式

选手可以在本题目录下使用如下命令编译得到可执行文件：

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

对于编译得到的可执行文件 segment：

• 可执行文件将从标准输入读入以下格式的数据：
  • 第一行包含两个非负整数 $c,t$。
  • 接下来依次为每组测试数据。对于每组测试数据：
    • 第一行包含三个正整数 $n,m,k$。
    • 第 $i+2$（$0\le i<n$）行包含两个正整数 $l_i,r_i$。
• 可执行文件将输出以下格式的数据至标准输出：
  • 对于每组测试数据，输出一行 $k$ 个非负整数 $a_1,a_2,\ldots,a_k$。

输出格式

无

输入输出样例 #1

输入 #1

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

输出 #1

3 3 0
4 3 2 1
4 6 0

说明/提示

【样例 $1$ 解释】

对于第一组测试数据：

• 大小为 $1$ 的集合有 $\{0\},\{1\},\{2\}$，均是优美的。
• 大小为 $2$ 的集合有 $\{0,1\},\{1,2\},\{0,2\}$，均是优美的。
• 大小为 $3$ 的集合有 $\{0,1,2\}$，构造出的图是一个三元环，不是优美的。

因此答案分别为 $3,3,0$。

对于第二组测试数据：

• 大小为 $1$ 的集合中，所有 $4$ 个集合均是优美的。
• 大小为 $2$ 的集合中，$\{0,1\},\{1,2\},\{2,3\}$ 是优美的。
• 大小为 $3$ 的集合中，$\{0,1,2\},\{1,2,3\}$ 是优美的。
• 大小为 $4$ 的集合 $\{0,1,2,3\}$ 是优美的。 因此答案分别为 $4,3,2,1$。

【样例 $2$】

见选手目录下的 segment/segment2.in 与 segment/segment2.ans。

该样例满足测试点 $6\sim8$ 的约束条件。

【样例 $3$】

见选手目录下的 segment/segment3.in 与 segment/segment3.ans。

该样例满足测试点 $9,10$ 的约束条件。

【样例 $4$】

见选手目录下的 segment/segment4.in 与 segment/segment4.ans。

该样例满足测试点 $11\sim15$ 的约束条件。

【样例 $5$】

见选手目录下的 segment/segment5.in 与 segment/segment5.ans。

该样例满足测试点 $16\sim18$ 的约束条件。

【样例 $6$】

见选手目录下的 segment/segment6.in 与 segment/segment6.ans。

该样例满足测试点 $22,23$ 的约束条件。

【样例 $7$】

见选手目录下的 segment/segment7.in 与 segment/segment7.ans。

该样例满足测试点 $24,25$ 的约束条件。

【数据范围】

设 $K$ 为单个测试点内所有测试数据的 $k$ 的和。对于所有测试数据，均有：

• $1\le t\le20$；
• $1\le n\le3000$，$1\le m\le10^3$，$1\le k\le n$，$K\le200$；
• 对于所有 $0\le i<n$，均有 $1\le l_i\le r_i\le m$。

::cute-table{tuack}

• 特殊性质 $A$：对于所有 $0\le i,j<n$ 且 $i\ne j$，均有线段 $i$ 不包含线段 $j$，即 $l_i>l_j$ 或 $r_i<r_j$。
• 特殊性质 $B$：对于所有 $0\le i<j<n$，均有线段 $i$ 包含线段 $j$，或线段 $i$ 与线段 $j$ 不相交，即 $l_i\le l_j\le r_j\le r_i$、$r_i<l_j$ 或 $l_i>r_j$。
• 特殊性质 $C$：$n$ 条线段的全部 $2n$ 个端点互不相同，即 $l_0,l_1,\ldots,l_{n-1},r_0,r_1,\ldots,r_{n-1}$ 两两不同。

附件下载

segment.zip 805.24KB