P15773 [JAG 2025 Summer Camp #2] Count Unique Packing

你在“容器装箱可识别性中心”工作，研究容器装箱方案的唯一性。 给定 $N$ 件物品。第 $i$ 件物品有一个正整数重量 $A_i$（$1 \leq i \leq N$）。 你考虑将物品的一个（非空）子集 $S \subseteq \{1, 2, \ldots, N\}$ 装入容器。你可以使用任意多个非空容器（不允许使用空容器）。固定一个正整数 $w$ 表示每个容器的容量。$S$ 的一个**有效装箱**是将 $S$ 中的物品分配到容器中的一种方案，它必须满足以下所有条件： - **覆盖性**：$S$ 中的每件物品恰好被放入一个容器。 - **容量限制**：每个容器中物品的总重量不超过 $w$。 - **不可合并性**：对于任意两个不同的容器 $A$ 和 $B$，$A$ 或 $B$ 中所含物品的总重量**严格大于** $w$（即，在不违反容量 $w$ 的前提下，任意两个容器都无法合并成一个容器）。 容器是不可区分的，而物品是互不相同的（即使某些物品重量相同）。两种装箱方案被认为是相同的，当且仅当它们诱导出 $S$ 的相同划分；等价地说，对于任意不同的 $i, j \in S$，物品 $i$ 和 $j$ 在一种装箱方案中位于同一个箱子，当且仅当它们在另一种装箱方案中也位于同一个箱子。 对于一个固定的 $w$，如果一个子集 $S$ 恰好存在一种满足所有条件的有效装箱方案，则称 $S$ 是**唯一可装箱的**。 给定一个整数 $W$。令 $f(w)$（$w = 1, 2, \ldots, W$）表示容量为 $w$ 时唯一可装箱的非空子集的数量。对于每个 $w = 1, 2, \ldots, W$，输出 $f(w)$ 对 $998244353$ 取模的结果。换句话说，对于每个 $w = 1, 2, \ldots, W$，定义 $$ f(w) = \#\{S \subseteq \{1, 2, \ldots, N\} \mid S \text{ 是非空的，且对于容量 } w \text{ 是唯一可装箱的}\}. $$ 输出 $W$ 个整数；对于每个 $w = 1, 2, \ldots, W$，输出 $f(w)$ 对 $998244353$ 取模的结果。

输入包含一个测试用例，格式如下。 $$ \begin{aligned} & N \ W \\ & A_1 \ A_2 \ \cdots \ A_N \end{aligned} $$ 第一行包含两个整数 $N$（$1 \leq N \leq 5000$）和 $W$（$1 \leq W \leq 5000$），分别表示物品的数量和容量参数 $w$ 的上界（即需要考虑的最大容量）。第二行包含 $N$ 个正整数 $A_1, A_2, \ldots, A_N$（$1 \leq A_i \leq W$）。每个 $A_i$ 表示物品 $i$ 的重量。

在一行中输出 $W$ 个整数，以空格分隔：对于每个 $w = 1, 2, \ldots, W$，第 $w$ 个整数是 $f(w)$ 对 $998244353$ 取模的结果（容量为 $w$ 时的答案）。

翻译由 DeepSeek V3.2 完成