ABC 321 F #(subset sum = K) with Add and Erase

题意
有一个箱子，每次可以向里面添加或者拿走一个数，问每次操作过后，任选箱子里的数相加，总和等于k的方案数是多少。

思路
萌新算是学到新东西了，这其实是个可撤销背包的板题。
我们先考虑一个问题:
对于普通计数类dp，我们现在禁用某一个数i，我们现在想知道某一个数j有多少种方式表示（即dp[j]）。那么我们现在正常进行一次计数dp，然后撤销使用了数字i的方案即可。

• 若j<i，那么dp[j]是不会变化的，因为j不可能表示为i加上其它正整数的和
• 若j>=i,dp[j]就会包含选择了数字i的方案。那么这些方案一定是从dp[j-i]这个状态转移过来的。那么只需要减去dp[j-i]即可。
  对于本题，若操作为向集合里添加某个数，那么只需要从k到x遍历一遍dp,然后转移方程为dp[i]=dp[i-x]+dp[i];若在集合里删除某个数，那么只需要从x到k遍历一遍dp,然后转移方程为dp[i]=dp[i]-dp[i-x]。

难点
这个题真正值得关注的是如何理解遍历顺序（添加为倒序遍历，删除为正序遍历）：

• 若添加某个数，那么可以类比01背包，你只是增加了一个x，dp[i]的转移只是比原来多了一种路径（dp[i-x]+x），所以只需要将原来的dp[i-x]再加上一次就可以了，这也是保证了dp的无后效性，所以需要从后向前遍历。（如果你正向遍历，你就会多加很多次你添加的x，然后只多添加了一个x）
• 若删除某个数，那么此时就要考虑到前面的数的方案数对后面数的方案数的后效性了，因为你设想还是倒序遍历，当你更新dp[i]=dp[i]-dp[i-x]时，此时的i-x若仍然大于x，那么dp[i-x]也要发生变化，也就是先更新小的，再更新大的。（好好理解这两个遍历顺序）

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
const int maxn=2e5+10;
int dp[maxn];

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int q,k;
	cin>>q>>k;
	dp[0]=1;
	while(q--)
	{
		char s;
		int x;
		cin>>s>>x;
		if(s=='+')
		{
			for(int i=k;i>=x;i--)
			  dp[i]=(dp[i]+dp[i-x])%mod;
		}
		else 
		{
			for(int i=x;i<=k;i++)
			  dp[i]=(dp[i]-dp[i-x]+mod)%mod;
		}
		cout<<dp[k]%mod<<endl;
	}
	
	
	
	
	return 0;
}