题目描述
硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。每次带di枚ci硬币，买si的价值的东西。请问每次有多少种付款方法。
输入输出格式
输入格式：
第一行 c1,c2,c3,c4,tot 下面tot行 d1,d2,d3,d4,s
输出格式：
每次的方法数
输入输出样例
说明
di,s<=100000
tot<=1000
[HAOI2008]
这题容斥原理加背包
完全背包一维优化解释：
http://blog.csdn.net/howardemily/article/details/55223039
此题搬运大神思路
https://www.luogu.org/blog/IAmHellWord/solution-p1450
好巧妙的一道dp题！
如果我们就赤裸裸的多重背包那么就是O(10^5*10^5*1000)
一周的时间都运行不完（手动滑稽）！
那么怎么办呢？如果没有硬币数量的限制那就多好啊？直接一个完全背包预处理，然后O(1)输出就好了
可是有了硬币的限制怎么办？我们先考虑一个简单一点的情况：只有第一个硬币有限制。
如果我们用类似前缀和的思想（术语叫差分），我们先完全背包预处理好无限制的情况，拿dp[tot]减去dp[tot-c[i]*(d[i]+1)]就是我们所需的方案数。
这是为什么呢？为什么要弄个c[i]*(d[i]+1)？其实我们可以这样想，无限制的情况就是没有那个di，而有限制时，不应该计入答案的方案数就是把c[i]这个硬币取了超过d[i]次，对吧？那么我们手动先取出d[i]+1个c[i]的硬币，然后剩下的价值弄个完全背包，这时就是我们所不需要的答案， 把它减掉就行了。
答案为 面值S的总的没有硬币限制下的方案数 – 第1种硬币超过限制的方案数 – 第2种硬币超过限制的方案数 – 第3种硬币超过限制的方案数 – 第4种硬币超过限制的方案数 + 第1,2种硬币同时超过限制的方案数 + 第1,3种硬币同时超过限制的方案数 + …… + 第1,2,3,4种硬币全部同时超过限制的方案数。这就是大名鼎鼎的容斥原理啊！写成位运算就很优美了！
方案数会爆int哟。
参考代码（0表示满足限制，1表示不满足限制）：
#include <bits/stdc++.h> using namespace std; #define maxn 1000010 typedef long long ll; #define inf 2147483647 #define ri register int int c[maxn], d[maxn]; ll dp[maxn]; int tot = 0; int sum; int main() { ios::sync_with_stdio(false); // freopen("test.txt", "r", stdin); // freopen("outout.txt","w",stdout); for (int i = 1; i <= 4; i++) cin >> c[i]; cin >> tot; dp[0] = 1; for (int i = 1; i <= 4; i++) for (int j = c[i]; j <= 100001; j++) dp[j] += dp[j - c[i]]; while (tot--) { for (int i = 1; i <= 4; i++) cin >> d[i]; cin >> sum; ll res = 0; for (int i = 0; i <= 15; i++) {//二进制放四个空，遍历掉有无受限制的所有情况 ll t = sum; int cnt = 0; for (int j = 1; j <= 4; j++)//这里是用来移位抓取数的 &1 嘛 if ((i >> (j - 1)) & 1) { t -= c[j] * (d[j] + 1); cnt ^= 1; } if (t < 0)//t小于0一定没超的 continue; if (!cnt)//cnt用这种方式判奇偶，奇减偶加 res += dp[t];//如果谁都没有超，那么i=0的那次，res=dp[sum]就是正常没有限制情况下的答案 else res -= dp[t]; } cout << res << endl; } return 0; }