ABC321F 题解

可撤销背包的模板题。

如果没有减操作就是 \(01\) 背包，众所周知转移方程是 \(f[i]=f[i]+f[i-v]\)。

考虑减操作，对于一个重量 \(i\)，不选物品 \(v\) 的方案数是什么呢？

发现我们只需要把选 \(v\) 的方案去掉就好，那么转移方程就是 \(f[i]=f[i]-f[i-v]\)。

于是就做完了。

注意取模变正等等问题。

关于循环顺序：

• 加操作应该用“\(i-v\) 不含 \(v\)”更新，倒序循环。
• 减操作也要用“\(i-v\) 不含 \(v\)”更新，正序循环（先去掉前面的 \(v\)）。

code:

f[0]=1;
rep(i,q){
	cin>>op>>x;
	if(op=='+')
		for(int j=k;j>=x;j--) f[j]=pls(f[j],f[j-x]);
	else for(int j=x;j<=k;j++) f[j]=mns(f[j],f[j-x]);
	printf("%d\n",f[k]);
}

附比较漂亮的取模运算：

inline int pls(int a,int b){
	return (a+b>=mod?a+b-mod:a+b);
}
inline int mns(int a,int b){
	return (a-b<0?a-b+mod:a-b);
}