专栏文章

题解：AT_abc169_f [ABC169F] Knapsack for All Subsets

NN1tr0us_Acid
AT_abc169_f题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minql6yq
此快照首次捕获于
2025/12/02 06:44
3 个月前
此快照最后确认于
2025/12/02 06:44
3 个月前
查看原文
集训选了这题，遂写题解。

Solution\texttt{Solution}

不难发现，如果有一个集合 T0={x1,x2,...,xk}T_0=\{x_1, x_2,..., x_k\}，满足 ∑x∈T0Ax=S\sum_{x \in T_0} A_x = S，那么 T0T_0 对于所有满足 T0⊂TT_0 \subset T 的 TT 都会产生一次贡献。那么 T0T_0 的总贡献就是 2n−k2^{n - k}，因为除了 T0T_0 中必选的元素外，其他 n−kn - k 个元素可选可不选。
考虑 DP，我们令 fi,jf_{i,j} 表示我们从前 ii 个数里选数，和为 jj 的方案数，这里的 jj 只用统计到 SS 即可。那么我们可以得到以下转移：
fi,j=fi−1,j×2+fi−1,j−ai[j≥ai]f_{i, j}=f_{i-1,j} \times 2 + f_{i - 1, j - a_i}[j \geq a_i]
因为 fi−1,jf_{i-1,j} 是不选 aia_i 已经有 jj 了，所以当前为可选可不选，共两种情况。
初始化 f0,0=1f_{0, 0}=1。

Code\texttt{Code}

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...