题解：AT_abc169_f [ABC169F] Knapsack for All Subsets

· · 题解

集训选了这题，遂写题解。

\texttt{Solution}

不难发现，如果有一个集合 T_0=\{x_1, x_2,..., x_k\}，满足 \sum_{x \in T_0} A_x = S，那么 T_0 对于所有满足 T_0 \subset T 的 T 都会产生一次贡献。那么 T_0 的总贡献就是 2^{n - k}，因为除了 T_0 中必选的元素外，其他 n - k 个元素可选可不选。

考虑 DP，我们令 f_{i,j} 表示我们从前 i 个数里选数，和为 j 的方案数，这里的 j 只用统计到 S 即可。那么我们可以得到以下转移：

f_{i, j}=f_{i-1,j} \times 2 + f_{i - 1, j - a_i}[j \geq a_i]

因为 f_{i-1,j} 是不选 a_i 已经有 j 了，所以当前为可选可不选，共两种情况。

初始化 f_{0, 0}=1。

\texttt{Code}

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int n, s;
const int N = 3005;
int a[N];
int f[N][N];
const int mod = 998244353;
signed main(void) {
    ios :: sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> s;
    f[0][0] = 1;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    for (int i = 1; i <= n; i ++) {
        for (int j = 0; j <= s; j ++) {
            f[i][j] = f[i - 1][j] * 2;
            f[i][j] %= mod;
            if(j >= a[i]) f[i][j] = (f[i][j] + f[i - 1][j - a[i]]) % mod;
        }
    }
    cout << f[n][s] << endl;
    return 0;
}