【Luogu P1450】[HAOI2008] 硬币购物（dp，容斥）

题目

题目描述

共有 $4$ 种硬币。面值分别为 $c_1,c_2,c_3,c_4$。

某人去商店买东西，去了 $n$ 次，对于每次购买，他带了 $d_i$ 枚 $i$ 种硬币，想购买 $s$ 的价值的东西。请问每次有多少种付款方法。

输入格式

输入的第一行是五个整数，分别代表 $c_1,c_2,c_3,c_4,n$。

接下来 $n$ 行，每行有五个整数，描述一次购买，分别代表 $d_1,d_2,d_3,d_4,s$。

输出格式

对于每次购买，输出一行一个整数代表答案。

样例 #1

样例输入 #1

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

样例输出 #1

4
27
1
2

提示

数据规模与约定

• 对于 $100\%$ 的数据，保证 $1\le c_i,d_i,s\le 10^5$，$1\le n\le 1000$。

思路

orz dp，orz 容斥。
最简单的思路：每轮一次多重背包。时间复杂度直接寄掉。
我们发现，如果没有数量的限制，只需要 $O(maxs)$ 的预处理一遍完全背包，每轮 $O(1)$ 输出即可。
那我们就先做一遍完全背包，预处理处 $dp$ 数组，然后想办法把限制去掉。
我们总方案数为 $dp[s]$，现在我们需要减去不合法的方案数。
考虑容斥。用 总方案数 $-$ 只考虑一种硬币超额使用方案数 $+$ 只考虑两种硬币超额使用方案数 …（容斥做下去）
有硬币超额使用的方案数怎么做呢？
先从一个简单的情况想起：只有 $1$ 号硬币超额使用。那么不合法的情况即为 $dp[s-(d[1]+1)\times c[1]]$。
解释：不合法的情况，就是选择了多于 $d[1]$ 枚 $1$ 号硬币。那么我们先强制选 $d[1]+1$ 枚 $1$ 号硬币，剩下的再随便选，就是不合法的方案数了。
如果有多种硬币超额使用呢？和上面同理，$dp$ 的下标即为 $s$ 减去每种硬币的 $(d[i]+1)\ast c[i]$。注意如果下标小于 $0$ 了要 continue。
时间复杂度 $O(4\times maxs+2^4\times 4\times n)$。

收获：多重背包可以由完全背包+容斥得出。

代码

#include 
#define rep(i, a, b) for (register int i(a); i <= b; ++i)
#define per(i, a, b) for (register int i(a); i >= b; --i)
#define FILE(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define mem(a, x) memset(a, x, sizeof a)
#define pb push_back
#define umap unordered_map
#define pqueue priority_queue
#define mp make_pair
#define PI acos(-1)
#define int long long

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int c[5], n, dp[100005], d[5], s;

template <typename _T>
void rd(_T &x) {
    int f = 1; x = 0;
    char s = getchar();
    while (s > '9' || s < '0') {if (s == '-') f = -1; s = getchar();}
    while (s >= '0' && s <= '9') x = (x<<3)+(x<<1)+(s^48), s = getchar();
    x *= f;
}

template <typename _T>
void write(_T x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x/10);
    putchar(x%10+'0');
    return ;
}

signed main() {
	rep(i, 1, 4) rd(c[i]); rd(n);
	dp[0] = 1ll;
	rep(i, 1, 4) rep(j, c[i], 100000) dp[j] += dp[j-c[i]];
	rep(i, 1, n) {
		rep(j, 1, 4) rd(d[j]); rd(s);
		int ans = dp[s];
		rep(j, 1, (1<<4)-1) {
			int k = -1, x = s;
			rep(kk, 1, 4) {
				if (!((1<<(kk-1))&j)) continue;
				if (k == -1) k = 1;
				else k = -1;
				x -= (d[kk]+1)*c[kk];
			}
			if (x < 0) continue;
			ans -= k*dp[x];
		}
		printf("%lld\n", ans);
	}
    return 0;
}
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56