bzoj 1042: [HAOI2008]硬币购物

题目链接

bzoj1042

题解

如果没有个数限制就是一个完全背包
考虑利用全集减去超出限制的种数
利用容斥
减去一种金币超出的，加上两种金币超出的，减去三种.......

设(f(S))为 只有 S种金币超出的方案数,(g(S))为S中的金币超过方限制，其他随意的方案数
那么(sum_{Tsupseteq S}f left(T ight))
我们要求(fleft( emptyset ight))
求g(s)，吧(N)中减去(S)中选了(d_i+1)个的和，然后剩下的就是一个完全背包
预处理后容斥查询

code

#include<cstdio>

inline int read() {
	int x=0,f=1;
	char c=getchar() ;
	while(c<'0'||c>'9') {
		 if(c=='-')f=-1;
		 c=getchar();
	}
	while(c<='9'&&c>='0') {
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}const int maxn = 100001;
int M[6],N[6];
int f[maxn];
int tot,ned;
void init() {
	f[0]=1;
	for(int i=1;i<=4;++i)
		for(int j=M[i];j<maxn;++j) 
			f[j]+=f[j-M[i]];
}
int ans;
void solve(int rem,int cnt,int num) {
	if(num==5) {
		if(!cnt)return ;
		if(rem<0)return ;
		if(cnt&1) ans-=f[rem];
		else ans+=f[rem];
		return ;
	}
	solve(rem-((N[num]+1)*M[num]),cnt+1,num+1);
	solve(rem,cnt,num+1);
}
int main() {
	for(int i=1;i<5;++i) M[i]=read();
	tot=read();
	init();
	for(;tot--;) {
		for(int i=1;i<5;++i) N[i]=read();
		ned=read();ans=f[ned];
		solve(ans,0,1);
		printf("%d
",ans);
	}
	return 0;
}