問題はこちら
長さ の正整数列
に対して、その部分集合
を考える。その部分集合に含まれる部分集合
の和が
になるようなものの個数を求めよ。
考え方
集合単位でDPをしていくことを考える。部分集合に含まれる部分集合という考えが少し難しいが、入力例1を見れば概観が掴める。
dp[i + 1][j]
:0-indexで番目まで見たとき、和が
となるような
を含む
の場合の数。
- A[i] を
に含めないとき、
の和は
のまま。
に入れる or 入れないで二通りの可能性がある。よって、
dp[i + 1][j] += dp[i][j] *2
- A[i] を
に含めるとき、
の和は
になる。よって、
dp[i + 1][j + A[i]] += dp[i][j]
例えば、 が
、
のときを考えてみる。
dp[1][4]
:で、
の1通り
dp[2][4]
:dp[1][4]
で題意を満たしているもの対して、に 2を入れると
となる。入れないと
となる。いずれも
は
のままなので題意を満たすが、
dp[1][4]
のときと違い、に
を入れる場合が増えるため、
dp[2][4] += dp[1][4] * 2
解答
#include <bits/stdc++.h> using namespace std; using ll = long long; const ll mod = 998244353; #define rep(i, n) for (ll i = 0; i < (ll)(n); i++) int main() { ll n, s; cin >> n >> s; vector<ll> a(n); rep(i, n) cin >> a[i]; vector<vector<ll>> dp(n + 1, vector<ll>(s + 1)); dp[0][0] = 1; rep(i, n) { rep(j, s + 1) { dp[i + 1][j] += ((dp[i][j] * 2) % mod); 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; } } } cout << dp[n][s] << '\n'; return 0; }