[HAOI2008]硬币购物

洛咕

题意:硬币购物一共有(4)种硬币.面值分别为(c_1,c_2,c_3,c_4).某人去商店买东西，去了(tot)次.每次带(d_i)枚(c_i)硬币，买(s_i)的价值的东西.请问每次有多少种付款方法?(s_i<=100000).

分析:预处理没有硬币枚数限制时(即完全背包)买(x)元的方案数.然后容斥是否超过硬币的限制即可.

这道题的处理方式真的很妙,遇到这种本来有上界或者下界的东西,我们先求出它无限制时的答案,然后再容斥掉不符合限制的答案.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=100005;
int c[5],d[5];ll f[N];//记得开long long
int main(){
	c[1]=read();c[2]=read();c[3]=read();c[4]=read();
	int tot=read();f[0]=1;//完全背包初始化
	for(int i=1;i<=4;++i)
		for(int j=c[i];j<=N-5;++j)
			f[j]+=f[j-c[i]];//完全背包,f[j]表示买j元的方案数
	while(tot--){
		d[1]=read();d[2]=read();d[3]=read();d[4]=read();
		int sum=read();ll ans=0;
		for(int i=0;i<=15;++i){//15=(2^4)-1,二进制枚举
			ll t=sum;int cnt=0;
			for(int j=1;j<=4;++j){//判断是否有该种硬币的限制
				if(i&(1<<(j-1)))t-=c[j]*(d[j]+1),cnt^=1;
			}
			if(t<0)continue;//防止下面数组下标越界
			if(!cnt)ans+=f[t];
			else ans-=f[t];
		}
		printf("%lld
",ans);
	}
    return 0;
}