F - 所有子集的背包问题

得分：600分

问题描述

给定一个由$N$个正整数组成的序列$A_1$，$A_2$，$\ldots$，$A_N$，以及另一个正整数$S$。
对于集合$\{1, 2, \ldots , N \}$的非空子集$T$，我们定义$f(T)$如下：

• $f(T)$表示集合$T$中满足$A_{x_1}+A_{x_2}+\cdots +A_{x_k} = S$的不同非空子集$\{x_1, x_2, \ldots , x_k \}$的个数。

求所有$2^N-1$个$\{1, 2, \ldots , N \}$的子集$T$上的$f(T)$之和。由于这个和可能非常大，输出它取模$998244353$后的结果。

约束条件

• 输入中的所有值均为整数。
• $1 \leq N \leq 3000$
• $1 \leq S \leq 3000$
• $1 \leq A_i \leq 3000$

输入

输入的格式如下：

$N$ $S$

$A_1$ $A_2$ $...$ $A_N$

输出

输出$f(T)$之和，取模$998244353$后的结果。

3 4
2 2 4

6

对于每个$T$，$f(T)$的值如下所示。这些值的和为$6$。

• $f(\{1\}) = 0$
• $f(\{2\}) = 0$
• $f(\{3\}) = 1$ （集合$\{3\}$满足条件）
• $f(\{1, 2\}) = 1$ （$\{1, 2\}$）
• $f(\{2, 3\}) = 1$ （$\{3\}$）
• $f(\{1, 3\}) = 1$ （$\{3\}$）
• $f(\{1, 2, 3\}) = 2$ （$\{1, 2\}, \{3\}$）

5 8
9 9 9 9 9

0

10 10
3 1 4 1 5 9 2 6 5 3

3296