#528. [2024-11-12 P2] 壱雫空

[2024-11-12 P2] 壱雫空

题目描述

片场摆了那么多伞,能给大祥老师一把吗/kel

给定 n,mn,m ,现在有 nn 把伞,第 ii 把伞的质量是 aia_i 。对于 k=0,1,2,…,nk=0,1,2,\dots,n ,你需要解决以下问题:

计算有多少集合 S⊆{1,2,…,n}S\subseteq \{1,2,\dots,n\} 满足:存在 T⊆ST\subseteq S 使得 ∣T∣=∣S∣−k|T|=|S|-k 且

∑x∈Tax≥m\sum\limits_{x\in T}a_x\geq m 。

答案对 998244353998244353 取模。

输入格式

第一行两个整数 n,mn,m 。含义如题所示。

第二行包含 nn 个整数,第 ii 个整数表示 aia_i 。

输出格式

输出 n+1n+1 行,每行一个整数,第 ii 行的整数表示 k=i−1k=i-1 时的答案。

样例

样例输入

4 7
3 1 5 2

样例输出

6
4
1
0
0

数据范围

对于所有数据,1≤n,m≤3∗103,1≤ai≤3∗1031\le n,m\le 3*10^3,1\le a_i\le 3*10^3 。

子任务 1 ( 20% ) : 1≤n,m≤101\le n,m\le 10 。

子任务 2 ( 20% ) : 1≤n,m≤1001\le n,m\le 100 。

子任务 3 ( 20% ) : 1≤n,m≤3001\le n,m\le 300 。

子任务 4 ( 40% ) : 无特殊限制。