AT_ndpc2026_q 区間の和集合

给定一个整数 $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 \{1,2,\dots,N\}$ 中，有多少个子集满足下述条件？请将答案对 $998244353$ 取模后输出。 > > - 满足以下条件的整数 $m$（$1 \leq m \leq M$）的个数恰好为 $K$： > - 存在整数 $i \in S$，使得 $L_i \leq m \leq R_i$。

输入按如下格式从标准输入读入： > $N$ $M$ > $L_1$ $R_1$ > $L_2$ $R_2$ > $\vdots$ > $L_N$ $R_N$

输出 $M$ 行。在第 $i$ 行，输出对应 $K = i$ 的答案。

### 提示 本题对内存的限制非常严格。 ### 样例解释 1 当 $K=1$ 时，没有子集 $S$ 满足条件。 当 $K=2$ 时，有 $2$ 个这样的子集：$\{1\}, \{2\}$。 当 $K=3$ 时，有 $2$ 个这样的子集：$\{3\}, \{2,3\}$。 当 $K=4$ 时，有 $3$ 个这样的子集：$\{1,2\}, \{1,3\}, \{1,2,3\}$。 ### 约束条件 - $1 \leq N \leq 2000$ - $1 \leq M \leq 4000$ - $1 \leq L_i \leq R_i \leq M$ - 所有输入值均为整数。 由 ChatGPT 5 翻译