配点 : 100 点
問題文
长度为 N 的正整数序列 请解决以下有关 A=(A_1,A_2,\dots,A_N) 。k=0,1,\dots,N 的问题。
\lbrace 1,2,\dots,N\rbrace 的子集 计算满足以下条件的 S 的数量。 998244353 取余。起初,数列
- \left\vert T\right\vert=\left\vert S\right\vert-k 该组由 S 的子集 计算满足以下条件的 T 存在满足 \sum_{i \in T}A_{i}\ge M 的东西。
制約
- 1 \le N \le 3000
- 1 \le M \le 3000
- 1 \le A_i \le 3000
入力
输入是按以下格式从标准输入给出的。
N M A_1 A_2 \dots A_N
出力
N+1 跨线输出。 输出 i(1\le i\le N+1) 行中, k=i-1 的答案。 让我以
入力例 1
4 7 3 1 5 2
出力例 1
6 4 1 0 0
k=1 为例进行解释。
- S=\lbrace 1,3,4\rbrace 是 包含在T=\lbrace 3,4\rbrace 然后 \left\vert T\right\vert=\left\vert S\right\vert-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 。
入力例 2
1 5 7
出力例 2
1 0
入力例 3
9 18 1 9 5 6 2 7 1 4 8
出力例 3
346 309 230 126 46 10 1 0 0 0