洛谷—— P1450 [HAOI2008]硬币购物

时间:2022-03-02 12:00:12

P1450 [HAOI2008]硬币购物

硬币购物一共有$4$种硬币。面值分别为$c1,c2,c3,c4$。某人去商店买东西,去了$tot$次。每次带$di$枚$ci$硬币,买$si$的价值的东西。请问每次有多少种付款方法。

直接考虑有多少种方案数可行有点儿难,这时候就应该考虑容斥原理,即有多少人不可行,计算出总的方案数,容斥一下即可。

使用完全背包,计算总的方案数。

然后枚举每一种可能的情况,用总的方案数-第一枚硬币超过的方案数-第二枚。。。+第一枚和第二枚同时超过的方案数。。。以此类推

#include<bits/stdc++.h>

#define N 1000000
#define LL long long
using namespace std; int c[],T,S,d[];
LL f[N]; int main()
{
for(int i=;i<=;i++) scanf("%d",&c[i]); f[]=;
for(int i=;i<=;i++)
for(int j=c[i];j<=N/+;j++)
f[j]+=f[j-c[i]]; scanf("%d",&T);
while(T--)
{
for(int i=;i<=;i++) scanf("%d",&d[i]);
scanf("%d",&S);
LL ans=f[S];
for(int k=,i=;i<=;i++){
LL now=S;k=;//注意,k一定要还原
for(int j=;j<=;j++){
if((<<(j-))&i) k^=,now-=(d[j]+)*c[j];
}
if(now>=) k?ans-=f[now]:ans+=f[now];
}
printf("%lld\n",ans);
} return ;
}