题意

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

题解

一眼看去一个多重背包dp...再一眼看去数据范围..1e5这样暴力背包就t了.
可以转换想法，假设硬币的枚数没有限制，这样在每一组样例中，用不限制的总的数量减掉不满足条件的数量。
而不限制硬币个数的数量就可以用多重背包求解即可

    for(ll i = 0;i < 4;++i)
        for(ll j = 0;j < maxn;++j)
            if(j - c[i] >= 0) dp[j] += dp[j-c[i]];

接下来的问题就是如何找到针对每组数据不满足条件的付款方法，用总数减去即可。
考虑容斥定理，即，对于四种硬币可以看做四个集合，比如：即表示至少使用d0枚硬币买下东西，而满足条件情况的就是用所有情况减掉至少使用(d0+1)枚。但是考虑到，当减掉某两种不满足条件的情况时，我们将两集合的交集重复减掉了两遍，即需要使用容斥定理，将交集加回来。三种四种时同样。

而如何遍历这几种情况呢，可以将状态压缩为2进制表示，即1001就代表不满足第一种硬币和第四种硬币的情况，这样一共15种情况就可以表示为0001-1111 即遍历1-15，判断其二进制位即可。

code

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll maxn = 1e5 + 10;
ll dp[maxn];

int main()
{
    ll c[4];
    ll t;
    for(ll i = 0;i < 4;++i)cin>>c[i];
    cin>>t;
    dp[0] = 1;
    for(ll i = 0;i < 4;++i)
        for(ll j = 0;j < maxn;++j)
            if(j - c[i] >= 0) dp[j] += dp[j-c[i]];
    for(ll i = 0;i < t;++i){
        ll cnt[4];
        for(ll i = 0;i < 4;++i) scanf("%d",&cnt[i]);
        ll s;
        cin>>s;
        ll res = dp[s];
        for(ll i = 1;i <= 15;++i){
            ll tmp = 0;
            ll now = 0;
            for(ll j = 0;j < 4;++j){
                if((i >> j) & 1){
                    tmp++;
                    now += (cnt[j] + 1) * c[j];
                }
            }
            ll base = 1;
            if(tmp & 1) base = -1;
            if(s-now >= 0)res += base * dp[s - now];
        }
        printf("%lld\n",res); 
    }

    return 0;
}