Edit

【pythonでABC169を解説】F - Knapsack for All Subsets

問題概要

問題ページ

F - Knapsack for All Subsets
F - Knapsack for All Subsets

問題ページへ移動する

問題文

長さ \(N\) の正整数列 \(A_1\), \(A_2\), \(\ldots\), \(A_N\) と正の整数 \(S\) が与えられます。
集合\(\{1, 2, \ldots , N \}\) の空でない部分集合 \(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\) 通りありますが、そのすべてに対する \(f(T)\) の和を求めてください。ただし、答えは非常に大きくなることがあるので、\(998244353\) で割ったあまりを出力してください。

制約

  • 入力は全て整数である。
  • \(1 \leq N \leq 3000\)
  • \(1 \leq S \leq 3000\)
  • \(1 \leq A_i \leq 3000\)

問題の考察

ACコード

import sys


def solve():
    input = sys.stdin.readline
    mod = 998244353
    n, s = list(map(int, input().rstrip('\n').split()))
    a = list(map(int, input().rstrip('\n').split()))
    dp = [[0] * (s + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    for i in range(n):
        for j in range(s + 1):
            dp[i + 1][j] += dp[i][j] * 2
            dp[i + 1][j] %= mod
            if j + a[i] <= s:
                dp[i + 1][j + a[i]] += dp[i][j]
                dp[i + 1][j + a[i]] %= mod
    print(dp[-1][-1])


if __name__ == '__main__':
    solve()

-Edit
-