← 返回题目列表

AtCoder · npcapc_2024_b

B. 子集的某个总和

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

配点 : 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