题意#

题目链接 ↗

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

某人去商店买东西，去了 $n$ 次，对于每次购买，他带了 $d_i$ 枚第 $i$ 种硬币，想购买价值恰好为 $s$ 的东西。

多次询问，每次询问形如 $(d_1,d_2,d_3,d_4,s)$，求付款方法数。

$1\leq c_i,d_i,s\leq 10^5$，$1\leq n\leq 1000$.

题解#

先不考虑硬币个数限制，用 $f_i$ 表示随意凑出 $i$ 元的方案数，预处理出 $f$.

对每个硬币背包转移，若四种硬币面额为 $c_1,c_2,c_3,c_4$，则：

再看硬币个数的限制。

如果只有一种面值为 $c$ 的硬币，限制最多用 $d$ 枚，想要凑出 $s$ 元。

相较于所求，$f_s$ 中多余的部分，就是取出了至少 $(d+1)$ 枚硬币。

根据 $f_s$ 的定义可知，取至少 $(d+1)$ 枚硬币后凑出 $s$ 的方案数为 $f_{s-c\times(d+1)}$.

可以理解为：先花掉 $(d+1)$ 枚硬币，剩下随便凑。

所以只有一种硬币时，$\operatorname{Ans}=f-f_{s-c\times(d+1)}$.

现在就可以开始解决本题中四种硬币的情况了，也是同样的思路，考虑容斥。

直接这样减下去，同时不满足两个硬币的情况会重复，要加回来。

依次类推，同时不满足三个条件的要减下去，同时不满足四个的要加回来。

这个过程可以用二进制枚举方便地解决。

代码#

const int N = 1e5;
int n, c[4], d[4], s, ans;
int f[N + 10]; //f[s]表示：四种面值随便取，取出s的方案数量
signed main() {
	cin >> c[0] >> c[1] >> c[2] >> c[3] >> n;
	f[0] = 1;
	for(int i = 0; i < 4; i++) {
		for(int j = c[i]; j <= N; j++) {
			f[j] += f[j - c[i]];
		}
	}
	for(int i = 1; i <= n; i++) {
		cin >> d[0] >> d[1] >> d[2] >> d[3] >> s;
		ans = 0;
		for(int sta = 0; sta < (1 << 4); sta++) {
			int cnt = 0, sum = 0;
			for(int k = 0; k < 4; k++) {
				cnt ^= (1 & (sta >> k));
				sum += (1 & (sta >> k)) * c[k] * (d[k] + 1);
			}
			if(s - sum >= 0)
				ans += f[s - sum] * (cnt ? -1ll : 1ll);
		}
		cout << ans << endl;
	}
	return 0;
}