bzoj1402：[HAOI2008]硬币购物

思路：完全背包加容斥原理

首先不考虑限制，那么很容易可以预处理出f[i](f[i]+=f[i-c[i]],1<=i<=4,i-c[i]>=0)。

然后考虑如何求出限制后的答案。

首先考虑这样的一个问题：x1+x2+x3+x4+x5+...+xn=m有多少组整数解。显然插板法可以解决这个问题，但如果引入对于xi的限制，令xi不能超过ri，那么这个问题就应该要用到容斥原理了。

令Si为所有满足条件的xi的集合，那么这个问题就转化为了求所有Si的交集后再用插板法的一个问题了，瓶颈就在于如何求出Si的交集，于是可以考虑容斥原理，Si的交集即全集U-所有Si补集的并集，而Si的补集也就是满足xi>ri即xi>=ri+1的xi的集合，这样令所有的xi-=(ri+1)，也就是令m+=(ri+1)，然后即可用容斥原理加插板法求出所有Si补集的并集，全集U即原始问题的答案，那么这样运用容斥就完美地解决了这样一个问题。

再回到我们的问题，可以发现这就是刚刚提到的问题的每一个xi乘上一个权值，那么就令m+=(ri+1)*ci即可，于是对于所有询问均可做到O(1)回答。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define maxn 101000
 
int c[5],d[5],num[100],cases;
long long f[maxn];
 
int main(){
    for (int i=1;i<=4;i++) scanf("%d",&c[i]);scanf("%d",&cases);
    f[0]=1;
    for (int i=1;i<=4;i++)
        for (int j=c[i];j<=100000;j++)
            f[j]+=f[j-c[i]];
    num[0]=1;
    for (int i=1;i<(1<<4);i++) num[i]=num[i>>1]*((i&1)?-1:1);
    while (cases--){
        int sum;for (int i=1;i<=4;i++) scanf("%d",&d[i]);scanf("%d",&sum);long long ans=f[sum];
        for (int i=1;i<(1<<4);i++){
            int tmp=0;
            for (int j=0;j<5;j++)
                if ((1<<j)&i) tmp+=(d[j+1]+1)*c[j+1];
            if (sum>=tmp) ans+=f[sum-tmp]*num[i];
        }
        printf("%lld
",ans);
    }
    return 0;
}