Knapsack for All Subsets

题目描述

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

$f(T)$ 是满足 $A_{x_1}+A_{x_2}+\cdots +A_{x_k} = S$ 的、属于 $T$ 的不同非空子集 $\{x_1, x_2, \ldots , x_k \}$ 的数量。

求对所有 $2^N-1$ 个非空子集 $T$ 的 $f(T)$ 的总和。由于该和可能非常大，请对 $998244353$ 取模输出。

输入格式

输入从标准输入给出，格式如下： $N$ $S$ $A_1$ $A_2$ $...$ $A_N$

输出格式

输出对 $998244353$ 取模后的 $f(T)$ 之和。

3 4
2 2 4

6

5 8
9 9 9 9 9

0

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

3296

提示

输入中的所有数值均为整数。 $1 \leq N \leq 3000$ $1 \leq S \leq 3000$ $1 \leq A_i \leq 3000$对于每个 $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\}$）

标签: AtCoder|abc169F

来源

AtCoder|abc169F