問題
長さ $n$ の数列 $A$ と自然数 $s$ が与えられる。$\{ 1, \ldots , n \}$ の部分集合 $T$ について、$f(T)$ を $T$ の部分集合 $\{i _ 1, \ldots , i _ k\}$ で $A _ {i _ 1} + \cdots + A _ {i _ k} = s$ をみたすものの個数とするとき、すべての $T$ に対する $f(T)$ の和を求めよ。（$n,s,A _ i \leq 3000$）
解説
$\{ 1, \ldots , n \}$ の部分集合 $\{i _ 1, \ldots , i _ k\}$ で $A _ {i _ 1} + \cdots + A _ {i _ k} = s$ をみたすものそれぞれについて、$\{i _ 1, \ldots , i _ k\}$ を部分集合にもつような $\{ 1, \ldots , n \}$ の部分集合の個数を数え、それらを合計したものが求めたい答えに一致する。$\{i _ 1, \ldots , i _ k\}$ を部分集合にもつような $\{ 1, \ldots , n \}$ の部分集合の個数は $2 ^ {n - k}$ 個である。それらの合計を $DP[n][s]$ とする。
$n + 1$ が加わったとき、$\{ 1, \ldots , n + 1 \}$ の部分集合 $\{i _ 1, \ldots , i _ k\}$ で $A _ {i _ 1} + \cdots + A _ {i _ k} = s$ をみたすものを、$n + 1$ を含む方と含まない方に分ける。
$n + 1$ を含む方を部分集合にもつような $\{ 1, \ldots , n + 1 \}$ の部分集合の個数は、$\{ 1, \ldots , n \}$ の部分集合 $\{i _ 1, \ldots , i _ k\}$ で $A _ {i _ 1} + \cdots + A _ {i _ k} = s - A _ {n + 1}$ をみたすものを部分集合にもつような $\{ 1, \ldots , n \}$ の部分集合の個数に一致するので、それらの合計は $DP[n][s - A _ {n + 1}]$ である。
$n + 1$ を含まない方を部分集合にもつような $\{ 1, \ldots , n + 1 \}$ の部分集合の個数は、$\{ 1, \ldots , n + 1 \}$ の部分集合 $\{i _ 1, \ldots , i _ k\}$ で $A _ {i _ 1} + \cdots + A _ {i _ k} = s$ をみたすものを部分集合にもつような $\{ 1, \ldots , n + 1 \}$ の部分集合の個数 $2 ^ {n + 1 - k}$ に一致するので、 それらの合計は $2 \times DP[n][s]$ である。
以上より、
$$
DP[n+1][s] = DP[n][s - A _ {n + 1}] + 2 \times DP[n][s]
$$
実装
n, s = map(int, input().split()) *A, = map(int, input().split()) p = 998244353 DP = [[0 for j in range(s + 1)] for i in range(n + 1)] DP[0][0] = 1 for i in range(n): for j in range(s + 1): if j >= A[i]: DP[i + 1][j] = (2 * DP[i][j] + DP[i][j - A[i]]) % p else: DP[i + 1][j] = (2 * DP[i][j]) % p print(DP[n][s] % p)
