AdditionalFile5761.zip

#5761. 「NOI2026」线段

标签: 传统 | 时间限制: 2500 ms | 内存限制: 512 MiB |

题目描述

小 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$ 的集合是优美的。

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

实现细节

选手不需要，也不应该实现 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$ 的优美集合数量对 $998,244,353$ 取模后的结果。
• 对于每个测试点，该函数会被评测程序调用恰好 $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

输入

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

对于第一组测试数据：

• 大小为 $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\le 20$；
• $1\le n\le 3,000$，$1\le m \le 10^3$，$1\le k\le n$，$K\le 200$；
• 对于所有 $0\le i<n$，均有 $1\le l_i\le r_i\le m$。

测试点编号	$n\le$	$m\le$	$K\le$	$k\le$	特殊性质
$1\sim3$	$20$	$10^2$	$20$		无
$4,5$	$3,000$	$10^3$	$200$	$2$	^
$6\sim8$				$3$
$9,10$	$500$			$200$	A
$11\sim15$	$3,000$				B
$16\sim18$	$200$	$500$	$50$		C
$19\sim21$	$500$	$10^3$	$200$
$22,23$	$10^3$	$10^2$	$30$		无
$24,25$	$3,000$	$10^3$	$200$

特殊性质 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}$ 两两不同。