Luogu P1450 [HAOI2008]硬币购物 背包+容斥原理

时间：2022-03-03 13:12:22

考虑如果没有个数的限制，那么就是一个完全背包，所以先跑一个完全背包，求出没有个数限制的方案数即可。

因为有个数的限制，所以容斥一下：没有1个超过限制的方案=至少0个超过限制-至少1个超过限制+至少2个超过限制-至少3个超过限制+至少4个超过限制

如何求上面的方案数？有限制时，把$c[i]$这个硬币取了超过$d[i]$次是不应该有贡献的，那么我们先取出$d[i]+1$个价值为$c[i]$的硬币，然后剩下的就是$f[sum-c[i]*(d[i]+1)]$，这就是我们所不需要的答案， 把它按容斥的思路搞掉就行了。

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<cctype>

#include<cstdlib>

#include<vector>

#include<map>

#include<set>

#define ll long long

#define R register int

static char B[<<],*S=B,*D=B;

#define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin))?EOF:*S++)

using namespace std;

inline int g() {

    R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;

    do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;

}

const int N=;

int n,tot;

int c[],d[];

ll f[N+];

signed main() {

    for(R i=;i<=;++i) c[i]=g(); tot=g(); f[]=;

    for(R i=;i<=;++i) for(R j=c[i];j<=N;++j) f[j]+=f[j-c[i]];

    while(tot--) {

        for(R i=;i<=;++i) d[i]=g(); register ll sum=g(),ans=;

        for(R i=;i<=;++i) { R cnt=; register ll t=sum;

            for(R j=;j<=;++j) if(i&(<<(j-))) t-=c[j]*(d[j]+),cnt^=;

            if(t<) continue; cnt?ans-=f[t]:ans+=f[t];

        } printf("%lld\n",ans);

    }

}

2019.06.02

相关文章