[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\n",ans);
    }
    return 0;
}