AT_abc169_f [ABC169F] Knapsack for All Subsets

题目描述

给定一个长度为 $N$ 的正整数序列 $A_1, A_2, \ldots, A_N$ 和一个正整数 $S$。
对于集合 $\{1, 2, \ldots, N\}$ 的所有非空子集 $T$，定义 $f(T)$ 如下：

• $f(T)$ 为 $T$ 的所有非空子集 $\{x_1, x_2, \ldots, x_k\}$ 中，满足 $A_{x_1} + A_{x_2} + \cdots + A_{x_k} = S$ 的子集个数。

所有可能的 $T$ 有 $2^N-1$ 种，请计算所有 $T$ 的 $f(T)$ 之和。由于答案可能非常大，请输出其对 $998244353$ 取模的结果。

输入格式

输入以以下格式从标准输入给出。

$N$ $S$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

请输出所有 $T$ 的 $f(T)$ 之和对 $998244353$ 取模的结果。

输入输出样例 #1

输入 #1

3 4
2 2 4

输出 #1

6

输入输出样例 #2

输入 #2

5 8
9 9 9 9 9

输出 #2

0

输入输出样例 #3

输入 #3

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

输出 #3

3296

说明/提示

限制条件

• 输入均为整数。
• $1 \leq N \leq 3000$
• $1 \leq S \leq 3000$
• $1 \leq A_i \leq 3000$

样例解释 1

可以分别计算如下，和为 $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\}$ 这两个子集）

由 ChatGPT 4.1 翻译