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$ 时的答案。

## 部分分数 本题包含部分分数： - 如果你能解决所有 $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 翻译