题目地址：洛谷：【P1450】[HAOI2008]硬币购物 – 洛谷、BZOJ：Problem 1042. — [HAOI2008]硬币购物

题目描述

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

输入输出格式

输入格式：
第一行 c1,c2,c3,c4,tot 下面tot行 d1,d2,d3,d4,s

输出格式：
每次的方法数

输入输出样例

输入样例#1：

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

输出样例#1：

4
27

说明

di,s<=100000
tot<=1000
[HAOI2008]

题解

每次询问对着跑一遍背包并不现实，所以我们换一种思路。我们预处理不带硬币限制的背包方案数，并且考虑一个容斥的思路。假如不带限制的答案是$dp[s]$，第$i$种硬币限制了$d_i$个，那么从$d_i+1$往后的所有方案都是不可行的，因此要从不带限制的答案中减去一个$dp[s – c_i(d_i+1)]$。这样的话，会减重两个硬币都超了的方案，因此要加上$dp[s – c_i(d_i+1) – c_j(d_j+1)]$，以此类推。
复杂度$O(4 \times 100000 + tot \cdot 2^4)$。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 100005;

int c[5], d[5], tot, s, cnt[1 << 4 + 5];
LL dp[MAXN];

int main() {
    for(int i = 1; i < 1 << 4; i++) {
        cnt[i] = cnt[i >> 1] + (i & 1);
    }
    for(int i = 1; i <= 4; i++) {
        c[i] = readint();
    }
    dp[0] = 1;
    for(int i = 1; i <= 4; i++) {
        for(int j = c[i]; j < MAXN; j++) {
            dp[j] += dp[j - c[i]];
        }
    }
    tot = readint();
    while(tot--) {
        for(int i = 1; i <= 4; i++) {
            d[i] = readint();
        }
        s = readint();
        LL ans = dp[s];
        for(int i = 1; i < 1 << 4; i++) {
            int neg = (cnt[i] & 1) ? -1 : 1;
            int res = 0;
            for(int j = 1; j <= 4; j++) {
                if(i & (1 << (j - 1))) {
                    res += c[j] * (d[j] + 1);
                }
            }
            if(s >= res) ans += neg * dp[s - res];
        }
        printf("%lld\n", ans);
    }
    return 0;
}