P1450 [HAOI2008] 硬币购物
2026-05-09
题目大意
有四种面值的硬币 d1,d2,d3,d4,给出 n 个询问,每个询问包含四种硬币的个数 c1,c2,c3,c4 和正整数 S,求用这些硬币恰好凑出 S 的方案数。
其中 n≤103,ci,di,S≤105。
题解
由于不能对于每个询问单独计算,考虑扔掉数量限制,设 f[n] 表示用四种硬币不限个数凑出 n 的方案数。
现在对于每个询问,考虑根据几种硬币超出使用限制进行容斥,容易发现答案为总方案数减一种硬币超出限制,加两种硬币超出限制,减三种硬币超出限制,加四种硬币超出限制。
代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long LL;
const int N = 1e3+10 , M = 1e5+10;
int n , s;
int d[4] , c[4];
LL f[M];
int main() {
for(int i = 0 ; i < 4 ; i ++)
scanf("%d" , &d[i]);
f[0] = 1;
for(int i = 0 ; i < 4 ; i ++)
for(int j = 1 ; j < M ; j ++)
if(j >= d[i]) f[j] += f[j-d[i]];
scanf("%d" , &n);
while(n --) {
for(int i = 0 ; i < 4 ; i ++)
scanf("%d" , &c[i]);
scanf("%d" , &s);
LL ans = 0;
for(int i = 0 ; i < (1<<4) ; i ++) {
LL tmp = s; bool x = 0;
for(int j = 0 ; j < 4 ; j ++) {
if((i >> j) & 1) tmp -= 1ll*d[j]*(c[j]+1) , x ^= 1;
}
if(tmp >= 0) {
if(x) ans -= f[tmp];
else ans += f[tmp];
}
}
printf("%lld\n" , ans);
}
return 0;
}