【HAOI2008】硬币购物

Description

【HAOI2008】硬币购物

给定4种硬币的价值。若干组询问，每次给出4种硬币的数量和要购买的花费，求恰好购买的方案数

Solution

背包dp计数+容斥

如果不考虑硬币数量的限制，那么这个问题就是完全背包方案数问题，一遍dp就可以解决

现在加上数量的限制，那么合法方案数就是总数-非法方案数

总数很简单，就是完全背包方案总数

考虑非法方案数，如果一个方案非法，肯定有一种或几种硬币超出限制，那么我们假定他们用了max+1

那么利用容斥原理，非法方案数=一种硬币超出-两种硬币超出+三种硬币超出……

时间复杂度$O(4maxS+tot imes 4 imes 2^4)$

Code

#include <bits/stdc++.h>
namespace shl {
    typedef long long ll;
    const int S = 1e5 + 10;
    int c[5], tot, d[5], s;
    ll f[S];
    inline int read() {
        int ret = 0, op = 1;
        char c = getchar();
        while (!isdigit(c)) {
            if (c == '-') op = -1; 
            c = getchar();
        }
        while (isdigit(c)) {
            ret = (ret << 3) + (ret << 1) + c - '0';
            c = getchar();
        }
        return ret * op;
    }
    int main() {
        for (register int i = 0; i < 4; ++i) c[i] = read();
        f[0] = 1ll;
        for (register int i = 0; i < 4; ++i)
            for (register int j = c[i]; j < S; ++j)
                f[j] += f[j - c[i]];
        tot = read();
        while (tot--) {
            for (register int i = 0; i < 4; ++i) d[i] = read();
            s = read();
            ll ans = f[s];
            for (register int i = 1; i < 16; ++i) {
                ll sum = s; 
                int op = 0;
                for (register int j = 0; j < 4; ++j)
                    if (i & (1 << j)) {
                        sum -= (d[j] + 1) * c[j];
                        op ^= 1;
                    }
                if (sum < 0) continue ;
                if (op) ans -= f[sum];
                else ans += f[sum];
            } 
            printf("%lld
", ans);
        }
        return 0;
    }
};
int main() {
    shl :: main();
    return 0;
}