欢迎访问~原文出处——博客园-zhouzhendong
去博客园看该题解
题目传送门 - BZOJ1042
题目概括
硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。每次带di枚ci硬币，买si的价值的东西。请问每次有多少种付款方法。
题解
一开始没看数据范围，觉得是类似状压的dp。
然后看了看数据范围，懵逼了。
然后发现可以写容斥！
我们先当作完全背包，不考虑限制，把花费每种价格的方案数弄出来。
然后容斥一下就可以了。
具体容斥：所有情况 - 第一种货币超限的 - 第二种货币超限的…… + 第1、2种货币都超限的………………
代码
连续5次1A了，庆祝一下。
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
typedef long long LL;
const int N=,N_size=N+;
int c[],tot,d[],s;
LL dp[N_size];
int main(){
scanf("%d%d%d%d%d",&c[],&c[],&c[],&c[],&tot);
memset(dp,,sizeof dp);
dp[]=;
for (int i=;i<;i++)
for (int j=;j<=N;j++)
if (j+c[i]<=N)
dp[j+c[i]]+=dp[j];
while (tot--){
scanf("%d%d%d%d%d",&d[],&d[],&d[],&d[],&s);
LL ans=;
for (int i=;i<(<<);i++){
int v=s,cnt=;
for (int j=;j<;j++)
if ((i>>j)&)
cnt++,v-=(d[j]+)*c[j];
if (v<)
continue;
if (cnt&)
ans-=dp[v];
else
ans+=dp[v];
}
printf("%lld\n",ans);
}
return ;
}