分数: 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