[洛谷 1450][HAOI2008]硬币购物

题目链接

https://www.luogu.org/problem/P1450

题解

用 \(f[i]\) 表示在不限制各硬币使用数量的情况下支付的方案数，这个可以用完全背包预处理出来。

接下来考虑数量限制。先从单个硬币有限制开始：我们可以推出，在第 \(i\) 种硬币限定取 \(d[i]\) 个的时候，超出该限制的方案数为 \(f[s-(d[i]+1)*c[i]]\)。

这个式子的意义是明显的：我们强行让第 \(i\) 种硬币取 \(d[i]+1\) 个，剩下面额再跑完全背包得出的方案肯定是不合法的。

假如多个面额都有限制呢？简单地在总方案数上减去这几种不合法方案的数量是不合适的，因为可能有违反多个限制的方案被重复减去。

看到这里，我们想到了容斥原理。

我们将同时违反偶数个限制的方案数加上，把同时违反奇数个方案数限制的方案数减去，这些方案数的计算方法和上面单个硬币的限制是相同的。

我们可以通过二进制枚举子集来描述这样的限制。

#include <iostream>
#include <algorithm>
using namespace std;
long long c[5],d[5],f[100005],t,s;
int main()
{
 for(int i=1;i<=4;i++)
  cin>>c[i];
 cin>>t;
 f[0]=1;
 for(int i=1;i<=4;i++)
  for(int j=c[i];j<=100000;j++)
   f[j]+=f[j-c[i]];
 while(t--)
 {
  for(int i=1;i<=4;i++)
   cin>>d[i];
  cin>>s;
  long long ans=f[s];
  for(int i=1;i<=15;i++)
  {
   int x=s,tmp=i,cur=1,cnt=0;
   while(tmp)
   {
    if(tmp&1)x-=(d[cur]+1)*c[cur],cnt++;
    cur++;
    tmp>>=1;
   }
   if(x>=0)ans+=(cnt&1)?-f[x]:f[x];
  }
  cout<<ans<<endl;
 }
 return 0;
}