AT_fps_24_u 録画機

题目描述

我们将以下内容定义为一个子问题：

有 $N$ 个节目，编号为 $1$ 到 $N$。第 $i$ 个节目的播放时间为 $A_i$ 到 $B_i$。
你需要使用 $2$ 台录像机来录制所有节目。

对于一个节目集合 $S$，该集合内的所有节目能够被一台录像机全部录制的条件是：集合内任意两个节目在时间上没有重叠。（如果仅在端点处相接，也是允许的。）

• 更正式地说，集合 $S$ 内的所有节目可以被录制，当且仅当不存在不同的 $i, j \in S$ 使得 $\max(A_i, A_j) < \min(B_i, B_j)$。

现在，请判断是否可以只用 $2$ 台录像机录制下所有的节目。
更具体地说，是否存在一个对 ${1, 2, \dots, N}$ 的划分 $S_1, S_2$，使得 $S_1$ 和 $S_2$ 各自都能被一台录像机录制？
如果可以，输出 Yes，否则输出 No。

• $0 \leq A_i < B_i \leq T$
• $N, T, A_i, B_i$ 均为整数

你将得到 $N$ 和 $U$。
对于每一个 $T = 1, 2, \dots, U$，解决如下问题：

• 设此时 $N, T$ 与子问题相同。那么，所有可能的输入 $(A_1, B_1), \dots, (A_N, B_N)$ 的数量是 $\left(\dfrac{T(T+1)}{2}\right)^N$。
  其中，统计有多少种情况下子问题的答案为 Yes，并输出该结果对 $998244353$ 取模。

输入格式

输入格式如下，从标准输入读入：

$N$ $U$

输出格式

输出 $U$ 行。第 $i$ 行输出 $T=i$ 时的答案。

输入输出样例 #1

输入 #1

3 4

输出 #1

0
12
114
558

输入输出样例 #2

输入 #2

7 10

输出 #2

0
0
0
6300
260820
4161780
39414060
265208580
398083867
112841142

说明/提示

部分分数

本题包含部分分数：

• 如果你能解决所有 $N \leq 5 \times 10^3$ 且 $U \leq 5 \times 10^3$ 的数据，将获得 $4$ 分。

样例解释 1

例如，当 $T=2$ 时，存在一种可能输入为 $(A_1, B_1) = (0, 2)$、$(A_2, B_2) = (0, 1)$、$(A_3, B_3) = (1, 2)$，这样就满足条件。

数据范围

• $1 \leq N \leq 6 \times 10^4$
• $1 \leq U \leq 6 \times 10^4$
• $N, U$ 均为整数

由 ChatGPT 5 翻译