← 返回题目列表

AtCoder · fps_24_u

U. 录音机

中文机器翻译题面 查看原题

分数: 7 点

问题陈述

我们将以下定义为 子问题:

有 N 程序编号 1 通过 N.程序 i 播出时间 A_i 到时间 B_i.
您想要使用以下方式录制所有节目 2 录音机。

对于一组程序 S,条件是所有程序都在 S 可以用单个录音机录制的是,不能同时录制两个节目 S 时间重叠。 (如果它们仅在端点处接触也是可以接受的。)

  • 更正式地说,所有程序 如果没有明显的差异,可以记录 S 如果没有明显的情况可以记录 i, j \in S 这样 \max(A_i, A_j) < \min(B_i, B_j) 成立。

问题是是否可以使用以下方式录制所有节目 2 录音机。
更准确地说,是否存在分区 S_1, S_2 of {1, 2, \dots, N} 这样两者 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) is \left(\dfrac{T(T+1)}{2}\right)^N.
    其中,统计有多少个得出答案 子问题中的 Yes ,并输出结果模 998244353.

约束

  • 1 \leq N \leq 6 \times 10^4
  • 1 \leq U \leq 6 \times 10^4
  • N, U 是整数

部分分数

该问题有部分评分:

  • 如果您使用以下方法求解所有数据集 N \leq 5 \times 10^3 和 U \leq 5 \times 10^3,您将获得 4 点。

输入

输入由标准输入给出,格式如下:

N U

输出

打印 U 行。上 i第行,输出答案 T = i.


示例输入 1

3 4

示例输出 1

0
12
114
558

例如,当 T=2,输入例如 (A_1, B_1) = (0, 2), (A_2, B_2) = (0, 1), (A_3, B_3) = (1, 2) 满足条件。


示例输入 2

7 10

示例输出 2

0
0
0
6300
260820
4161780
39414060
265208580
398083867
112841142