AT_npcapc_2024_b Some Sum of Subset

给定一个长度为 $N$ 的正整数序列 $A=(A_1,A_2,\dots,A_N)$。对于 $k=0,1,\dots,N$，请解答如下问题： > 对于 $ \lbrace 1,2,\dots,N\rbrace $ 的子集 $S$，满足下述条件的子集的个数除以 $998244353$ 的余数是多少？ > > - 存在 $S$ 的子集 $T$，满足 $|T|=|S|-k$ 且 $ \sum_{i \in T}A_{i}\ge M $。

输入按以下格式从标准输入中给出。 > $N\ M\ A_1\ A_2\ \dots\ A_N$

请输出 $N+1$ 行。在第 $i$ 行（$1\le i\le N+1$），输出 $k=i-1$ 时的答案。

### 样例解释 1 以 $k=1$ 为例进行说明。 - 对于 $S=\lbrace 1,3,4\rbrace$，取 $T=\lbrace 3,4\rbrace$ 时，满足 $|T|=|S|-1$ 且 $ \sum_{i\in T} A_i \ge 7$，因此满足条件。 除此之外，还有 $S=\lbrace 1,2,3\rbrace,\lbrace 2,3,4\rbrace,\lbrace 1,2,3,4\rbrace$ 共 $3$ 个满足条件的子集。所以，$k=1$ 时答案为 $4$。 ### 数据范围 - $1 \le N \le 3000$ - $1 \le M \le 3000$ - $1 \le A_i \le 3000$ 由 ChatGPT 5 翻译