← 返回题目列表

AtCoder · ndpc2026_q

Q. 区间并集

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

分数: 7 点

注意

这个问题有非常严格的内存限制。

问题陈述

给你一个整数 M 和 N 整数对 (L_1, R_1), \dots, (L_N, R_N).对于每个 i (1 \leq i \leq N),它认为 1 \leq L_i \leq R_i \leq M.

对于每个 K = 1, 2, \dots, M,解决以下问题:

有 2^N 可能的子集 S \subseteq \lbrace 1,2,\dots,N\rbrace。其中,满足以下条件的有多少?输出答案取模 998244353.

  • 整数个数 m (1 \leq m \leq M) 满足以下条件正好是 K:
    • 存在一个整数 i \in S 这样 L_i \leq m \leq R_i.

约束

  • 1 \leq N \leq 2000
  • 1 \leq M \leq 4000
  • 1 \leq L_i \leq R_i \leq M
  • 所有输入值均为整数

输入

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

N M
L_1 R_1
L_2 R_2
\vdots
L_N R_N

输出

打印 M 行。上 i第行,输出答案 K = i.


示例输入 1

3 4
1 2
3 4
2 4

示例输出 1

0
2
2
3

当 K=1,有 0 子集 S 满足条件。
当 K=2,有 2 这样的子集: \lbrace 1\rbrace , \lbrace 2\rbrace.
当 K=3,有 2 这样的子集: \lbrace 3\rbrace , \lbrace 2,3\rbrace.
当 K=4,有 3 这样的子集: \lbrace 1,2\rbrace , \lbrace 1,3\rbrace , \lbrace 1,2,3\rbrace.


示例输入 2

8 10
6 10
1 4
5 9
6 8
1 5
7 9
4 6
4 8

示例输出 2

0
0
3
2
15
25
26
20
72
92