AT_abc321_f [ABC321F] #(subset sum = K) with Add and Erase 题解

题目大意

现在有一个空箱子。给你两个数 \(Q, K\)，然后给你 \(Q\) 行，每一行代表一个操作：

• \(+ x\)，即向箱子里加一个权值为 \(x\) 的小球。

• \(- x\)，即从箱子里把权值为 \(x\) 的小球拿一个出来。保证合法，即箱子里一定有权值为 \(x\) 的小球。

每一次操作后你都需要输出存在多少种拿球的方案，使得你拿出的所有球的权值和为 \(K\)。答案对 \(998244353\) 取模。

\(1 \le Q, K, x \le 5000\)

题解

如果不是动态的话，明显是普通的 0-1 背包问题。

考虑怎么让 0-1 背包变得动态。

我们发现这其实就是一个加减物品的操作。

加物品非常简单，就是再在原基础上跑一遍 dp。

            for(int i = 5000; i >= x; -- i)
                if(dp[i - x])
                    dp[i] = (dp[i] + dp[i - x]) % mod;

减物品其实也不难。就相当于跑了一遍反着的加物品。换句话说，就是你要在原有的方案上，减去这个物品贡献的方案。

            for(int i = x; i <= 5000; ++ i)
                if(dp[i - x])
                    dp[i] = (dp[i] - dp[i - x] + mod) % mod;

注意一些细节。加物品需要从大往小枚举，防止算重，和普通 0-1 背包一样。而减物品需要为了防止算重需要从小到大枚举。

代码

#include <bits/stdc++.h>
#define int long long
#define M 10005
#define mod 998244353

using namespace std;

int Q, K, dp[M], x;
char ch;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> Q >> K;
    dp[0] = 1;
    for(int i = 1; i <= Q; ++ i) {
        cin >> ch >> x;
        if(ch == '+') {
            for(int i = 5000; i >= x; -- i)
                if(dp[i - x])
                    dp[i] = (dp[i] + dp[i - x]) % mod;
        }
        else
            for(int i = x; i <= 5000; ++ i)
                if(dp[i - x])
                    dp[i] = (dp[i] - dp[i - x] + mod) % mod;
        cout << dp[K] << '\n';
    }
}