假垃圾

tjx114514 · 2026-11-11 10:16:46 · 题解

创意 JAG 推荐题目之：假mirage，简称假垃圾。

看到这个唯一可装箱，一个想法是去刻画这个集合长什么样，然而并没有成功。

于是退而求其次，考虑怎么对于确定的子集 S，去生成一个有效装箱的方案。

我们可以胡出一种贪心：记原来的集合为 A，选出的集合为 a。将 a_i 从小到大排序，并判断能否装进一个容器，如果装不进去了那就装进一个新的容器。

接下来我们需要确保这是唯一的方案，也就是不能通过调整得到新方案。考虑在这基础上怎么调整出一个新方案。

从最小的值 a_1 入手，我们尝试把一个原本不与 a_1 放在一起的元素改为放在一起，然后正常贪心就能得到一个新方案。

也就是若存在 x 满足 a_1+a_x ≤ w 且 a_1+a_2+\dots+a_x>w，将 a_x 放到第一个插入，其余元素不变，就能得到一个新的方案。

所以不能得到新方案的条件即为

我们可以枚举 w，然后在排序后的原数组 A 钦点 A_i 作为 a_1，对所有 i < j , A_j ≤ w-A_i 的元素做背包表示是否选入集合，由于钦点了 A_i 作为 a_1，所以实际上的限制是选出元素的和不超过 w-A_i。

这个区间做背包时间复杂度会爆炸，但是注意到元素大小的限制和背包大小的限制是一样的，所以可以直接取后缀做背包，预处理复杂度 O(nw)。

然后上面的条件并没有对于 a_1+a_x > w 的元素做其它限制，找到 i < j , w-A_i < A_j ≤ w 的元素 A_j 个数，每个元素可选可不选，直接预处理 2 的次幂算即可。总时间复杂度 O(nw)。

看不懂一堆限制的可以自己推，细节可以看代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5005,mod=998244353;
int n,w,a[N],b[N][N],sum[N][N],pw[N];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    pw[0]=1;for(int i=1;i<N;i++) pw[i]=pw[i-1]*2%mod;
    cin>>n>>w;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    b[n+1][0]=1;
    for(int i=n;i>=1;i--){
        memcpy(b[i],b[i+1],sizeof(b[i]));
        memcpy(sum[i],sum[i+1],sizeof(sum[i]));
        for(int j=w;j>=a[i];j--)
            b[i][j]=(b[i][j]+b[i+1][j-a[i]])%mod;
        ++sum[i][a[i]];
    }
    for(int i=1;i<=n+1;i++)
        for(int j=1;j<=w;j++)
            b[i][j]=(b[i][j]+b[i][j-1])%mod,sum[i][j]+=sum[i][j-1];
    for(int m=1;m<=w;m++){
        ll ans=0;
        for(int j=1;j<=n&&a[j]<=m;j++){
            int num=sum[j+1][m]-sum[j+1][m-a[j]];
            ans=(ans+1ll*b[j+1][m-a[j]]*pw[num])%mod;
        }
        cout<<ans<<' ';
    }
    return 0;
}

好了题解结束，谢谢观看。