bzoj1042 / HAOI 2008 硬币购物（容斥原理

Description

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

Input

第一行 c1,c2,c3,c4,tot 下面tot行 d1,d2,d3,d4,s,其中di,s<=100000,tot<=1000

Output

每次的方法数

Sample Input

1 2 5 10 2

3 2 3 1 10

1000 2 2 2 900

Sample Output

4

27

分析

嘿嘿嘿容斥终于学有用了。
这题本质上求满足方程 $x_1{c}_1+x_2{c}_2+x_3{c}_3+x_4{c}_4=s$x1​c1​+x2​c2​+x3​c3​+x4​c4​=s 的解，限制条件是 $0\le x_i\le d_i$0≤xi​≤di​。
假设没有限制条件，这题就是一个完全背包。因此我们想办法往完全背包上靠。于是想到容斥原理。用总方案减去有 $x_i\ge d_i+1$xi​≥di​+1 的方案。后面就是一个容斥了。

代码如下

#include <bits/stdc++.h>
#define N 100005
#define LL long long
using namespace std;
int x[5], d[5];
LL f[N], t[17], s, ans;
int bit(int x){
	int s = 0;
	while(x){
		s++;
		x -= x&-x;
	}
	return s;
}
int main(){
	int i, j, n, m, T, cnt;
	for(i = 0; i < 4; i++) scanf("%d", &x[i]);
	scanf("%d", &T);
	f[0] = 1;
	for(i = 0; i < 4; i++)
		for(j = x[i]; j <= 100000; j++) f[j] += f[j - x[i]]; 
	while(T--){
		memset(t, 0, sizeof(t));
		for(i = 0; i < 4; i++) scanf("%d", &d[i]);
		scanf("%d", &s);
		ans = f[s];
		for(i = 0; i < 4; i++) t[1 << i] = (d[i] + 1) * x[i];
		for(i = 1; i < (1 << 4); i++){
			if(!t[i]) t[i] = t[i-(i&-i)] + t[i&-i];
			cnt = bit(i);
			if(s < t[i]) continue;
			if(cnt & 1) ans -= f[s - t[i]];
			else ans += f[s - t[i]];
		}
		printf("%lld\n", ans);
	}
	return 0;
}