P1450 HAOI2008 硬币购物

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<cstdio>
#define re register
#define int long long
const int MAXn = 4;
const int MAXn2 = 16;
const int MAXW = 1e5;

template <class T> 
inline void read(T &a) {
    register char c;while (c = getchar(), c < '0' || c > '9');register T x(c - '0');while (c = getchar(), c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);}a = x;  
}

int T, n = 4, W, w[MAXn + 10], cnt[MAXn + 10], d[MAXW + 10];
signed main() {
    read(w[1]), read(w[2]), read(w[3]), read(w[4]), read(T);
    d[0] = 1;
    for (re int i = 1; i <= n; ++i) {
        for (re int j = w[i]; j <= MAXW; ++j) {
            d[j] += d[j - w[i]];
        }
    }
    while (T--) {
        read(cnt[1]), read(cnt[2]), read(cnt[3]), read(cnt[4]), read(W);
        int ans = 0;
        for (re int i = 0; i < MAXn2; ++i) {
            int p = W;
            for (re int j = 1; j <= n; ++j) {
                if ((i >> (j - 1)) & 1) {
                    p -= w[j] * (cnt[j] + 1);
                }
            }
            if (p < 0) {
                continue;
            }
            ans += __builtin_popcount(i) & 1 ? -d[p] : d[p];
        }
        printf("%lld\n", ans);
    }
}