BZOJ1042 [HAOI2008]硬币购物【完全背包 + 容斥】_综合

1042: [HAOI2008]硬币购物

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 2924 Solved: 1802
[Submit][Status][Discuss]

Description

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

Input

　　第一行 c1,c2,c3,c4,tot 下面tot行 d1,d2,d3,d4,s,其中di,s<=100000,tot<=1000

Output

　　每次的方法数

Sample Input

1 2 5 10 2
3 2 3 1 10
1000 2 2 2 900

Sample Output

4
27

首先我们一次次做背包肯定T

考虑一次性做完完全背包，每次减去不合法的方案数

显然每次 ans = f[s] - 第一样物品超过限制的方案数 - 第二样物品超过限制的方案数 - 第三样物品超过限制的方案数 - 第四样物品超过限制的方案数 + 第一二样物品超过限制的方案数 + .......

具体超过限制的方案数怎么求？以第一个物品为例，就是f[s - (d[i] + 1) * c[i]]，就是我们先用上d[i] + 1个硬币，剩余的部分任意取，所得的方案数就是我们所求

这算法太巧妙了> <

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define fo(i,x,y) for (int i = (x); i <= (y); i++)
#define Redge(u) for (int k = head[u]; k != -1; k = edge[k].next)
using namespace std;
const int maxn = 100005,maxm = 100005,INF = 1000000000;
inline LL read(){LL out = 0,flag = 1;char c = getchar();while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}while (c >= 48 && c <= 57) {out = out * 10 + c - 48; c = getchar();}return out * flag;
}
LL f[maxn],C[5],d[5],S;
void cal(){f[0] = 1;for (int i = 1; i <= 4; i++)for (int j = C[i]; j <= 100000; j++)f[j] += f[j - C[i]];
}
int main()
{REP(i,4) C[i] = read();cal();int T = read();LL ans,flag,sum;while (T--){REP(i,4) d[i] = read(); S = read();ans = f[S];for (int s = (1 << 4) - 1; s > 0; s--){sum = 0; flag = 1;for (int i = 1; i <= 4; i++)if ((1 << i - 1) & s){sum += (d[i] + 1) * C[i];flag = -flag;}if (sum <= S) ans += flag * f[S - sum];}printf("%lld\n",ans);}return 0;
}