Luogu P1450 [HAOI2008]硬币购物

gate

背包dp+容斥，然而没想出来。
首先预处理出没有限制的方案数。
价值为(c_i)的硬币有(d_i)个，那么不合法的方案数即为(f[c_i*(d_i+1)])，因为若(c_i)超出限制，后面的再怎么选都是不合法的了。
但这样显然会有重复计算。所以，根据容斥原理，减去1种超限的，加上2种超限的，减去3种超限的，加上4种超限的。

for(int i = 1; i <= 15; i++) {
	k = 1;
	now = 0;
	for(int j = 1; j <= 4; j++)
		if((i >> (j-1)) & 1) {
			now += c[j]*(d[j]+1);
			k *= -1;
		}
	if(now <= s)
		sum += k * f[s-now];
}

用2进制表示状态，15=1111=四个都选。
用一个数字k记录奇偶（正负）
最后别忘了判断状态是否存在（now <= s），否则会re...

完整代码如下

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#define MogeKo qwq
using namespace std;

const int maxn = 1e5+10;

int n,s,c[5],d[5];
long long sum,k,now,f[maxn];

int main() {
	for(int i = 1; i <= 4; i++)
		scanf("%d",&c[i]);
	f[0] = 1;
	for(int i = 1; i <= 4; i++)
		for(int j = c[i]; j <= 100000; j++)
			f[j] += f[j-c[i]];
	scanf("%d",&n);
	while(n--) {
		for(int i = 1; i <= 4; i++)
			scanf("%d",&d[i]);
		scanf("%d",&s);
		sum = f[s];
		for(int i = 1; i <= 15; i++) {
			k = 1;
			now = 0;
			for(int j = 1; j <= 4; j++)
				if((i >> (j-1)) & 1) {
					now += c[j]*(d[j]+1);
					k *= -1;
				}
			if(now <= s)
				sum += k * f[s-now];
		}
		printf("%lld
",sum);
	}
	return 0;
}