[HAOI 2008] 硬币购物

知识点

完全背包、容斥原理、有界计数

解题思路

先按4种硬币做完全背包，ways[s]统计无限枚数下支付s的方法。每个查询枚举违反上限的币种集合，对集合中第i种预先拿走di+1枚，把目标金额减去相应总值，按集合大小奇偶加减ways[剩余金额]。

正确性说明

支付方案若同时在指定集合各币种上超限，扣掉各自di+1枚后，与无限枚数支付剩余金额的方案一一对应。容斥对所有超限集合交集交替求和，恰好留下全部未超限方案。

易错点

硬币种类即使面值相同也按不同类型计数；上限是di，扣的是di+1；金额负时贡献0；方案数用64位。

复杂度

预处理O(4S)，每查询O(16·4)，空间O(S)，S=100000。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);long long c[4];for(auto&x:c)cin>>x;int n;cin>>n;const int S=100000;vector<long long>dp(S+1);dp[0]=1;for(long long v:c)for(int s=v;s<=S;s++)dp[s]+=dp[s-v];while(n--){long long d[4],s;for(auto&x:d)cin>>x;cin>>s;long long ans=0;for(int mask=0;mask<16;mask++){long long rem=s;for(int i=0;i<4;i++)if(mask>>i&1)rem-=(d[i]+1)*c[i];if(rem>=0)ans+=(__builtin_popcount((unsigned)mask)&1)?-dp[rem]:dp[rem];}cout<<ans<<'\n';}}