HAOI2008 硬币购物

很经典的一道容斥题

先来看一个很经典的问题

$$ \sum_{i=1}^n x_i=s(x是正整数)$$

这个式子的$x$的解有多少个?

显然这个可以用背包计算

用$dp[k]$表示能表示出的和为$k$的解的数量，正序枚举$k$

$$ dp[k]=dp[k]+dp[k-money[i]] $$

其中$money[i]$是硬币的面值

接下来我们给他加上限制，规定第$i$个$x$的上界是$c[i]$

现在的$x$的解的总数可以用容斥原理进行计算

我们要求的东西是

$$ \left | \bigcap a_i\right | (a_i为第i个元素满足限制下的解集的集合)$$

也就等于

$$ \left | S \right |-\left | \bigcup {\overline a_i} \right |$$

首先我们计算出所有的可能的情况也就是全集$s$

接下来我们把不合法的情况减去

根据容斥定理显然有答案=总的情况$-1$个不满足条件的$+2$个不满足条件的$-3$个不满足条件的……

那么如果能很快的求出几个不合法集合的并集的话，这道题就可以很轻松的解决了

考虑几个不合法集合的并集也是一个等式的形式，不过有的x有下界，有的x没有下界

那么显然下界那部分对于每一个解都是存在的

那么我们可以把它减去

也就是这样的

$$\sum x_i=s-所有下界的和$$

这个玩意的所有解的数量我们已经用$dp$处理出来了，直接调用即可

所以最后只需要枚举子集，然后观察一下子集中元素的个数，套上一个容斥系数即可

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define ll long long
ll mz[5],dp[2000050],c[5];
ll ans,s;
int main()
{
    for(int i=1;i<=4;i++)scanf("%d",&mz[i]);
    dp[0]=1;
    for(int i=1;i<=4;i++)
        for(int k=mz[i];k<=100000;k++)
            dp[k]+=dp[k-mz[i]];
    int t;
    scanf("%d",&t);
    while(t--)
    {
        for(int i=1;i<=4;i++)scanf("%d",&c[i]);    
        scanf("%lld",&s);
        ans=dp[s];
        for(int i=1;i<(1<<4);i++)
        {
            ll tmp=0,js=0;
            for(int j=1;j<=4;j++)if(1<<(j-1)&i)js++,tmp+=(c[j]+1)*mz[j];
            if(tmp>s)continue;
            if(js%2==0)ans+=dp[s-tmp];
            else ans-=dp[s-tmp];
        }
        printf("%lld\n",ans);
    }
    return 0;
}