容斥+背包学习笔记

有时候，我们在做背包问题时会遇到如下情况，给你一大堆询问，要你求出满足某种限制，填满背包的方法数。

先来一道例题：

例题1：

P1450 [HAOI2008]硬币购物

乍眼一看似乎是一个裸的完全背包，但是注意到询问组数较多，每次跑一遍完全背包绝对会炸掉，考虑预处理出不带限制的方法数，然后用容斥除去不满足限制的方法。

预处理，用题目的四种硬币凑出 $x$ 元的钱共有 $f(x)$ 种方法：

inline void Init(){
    dp[0]=1;
    for (register int i=1;i<=4;++i){
        for (register int j=c[i];j<MAXN;++j){
            dp[j]+=dp[j-c[i]];
        }
    }
}

简单容斥：

for (register int i=0;i<16;++i){
    int f=1,sum=0;
    for (register int j=1;j<=4;++j){
        if (i&(1<<(j-1))) {
            f*=-1;
            sum+=(d[j]+1)*c[j];
        }
     }
     if (s-sum>=0) ans+=f*dp[s-sum];
}

为什么是 $(d[j]+1)*c[j]$ ，不妨考虑先用 $d[j]+1$ 个硬币 $j$ ，这样肯定是不符合的，所以要减去。

代码：

#include <bits/stdc++.h>
#define MAXN 100005
#define int long long
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
int c[5],d[5];
int dp[MAXN];
inline void Init(){
    dp[0]=1;
    for (register int i=1;i<=4;++i){
        for (register int j=c[i];j<MAXN;++j){
            dp[j]+=dp[j-c[i]];
        }
    }
}
#undef int
int main(){
#define int long long
    for (register int i=1;i<=4;++i) c[i]=read();
    Init();
    int tot=read();
    while (tot--){
        for (register int i=1;i<=4;++i) d[i]=read();
        int s=read();
        int ans=0;
        for (register int i=0;i<16;++i){
            int f=1,sum=0;
            for (register int j=1;j<=4;++j){
                if (i&(1<<(j-1))) {
                    f*=-1;
                    sum+=(d[j]+1)*c[j];
                }
            }
            if (s-sum>=0) ans+=f*dp[s-sum];
        }
        printf("%lld\n",ans);
    }
}

例题2:

P4141 消失之物

跟上面一样，先预处理出来没有任何限制的方法数，注意是01背包：

f[0]=1;
for (register int i=1;i<=n;++i){
    for (register int j=m;j>=w[i];--j){
        f[j]=(f[j]+f[j-w[i]])%MOD;
    }
}

这里的容斥就比较简单：

ans[i][0]=1;
for (register int j=1;j<w[i];++j){
     ans[i][j]=f[j];
}
for (register int j=w[i];j<=m;++j){
     ans[i][j]=(f[j]-ans[i][j-w[i]]+MOD)%MOD;//容斥一下
}

对于 $<w[i]$ 的情况，一定里面合法方案没有 $w[i]$ 这个物品，所以 $ans[i][j]=f[j]$

对于 $\geq w[i]$ 的情况，需要进行容斥， $ans[i][j]=f[j]-ans[i][j-w[i]]$ ，注意到是 $ans[i][j-w[i]]$ 而不是 $f[j-w[i]]$ ，原因是 $f[j-w[i]]$ 的方案里面可能包含 $w[i]$ 。

#include <bits/stdc++.h>
#define MAXN 2005
#define MOD 10
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
static int w[MAXN],f[MAXN],ans[MAXN][MAXN];
int main(){
    int n=read(),m=read();
    for (register int i=1;i<=n;++i) w[i]=read();
    f[0]=1;
    for (register int i=1;i<=n;++i){
        for (register int j=m;j>=w[i];--j){
            f[j]=(f[j]+f[j-w[i]])%MOD;
        }
    }
    for (register int i=1;i<=n;++i){
        ans[i][0]=1;
        for (register int j=1;j<w[i];++j){
            ans[i][j]=f[j];
        }
        for (register int j=w[i];j<=m;++j){
            ans[i][j]=(f[j]-ans[i][j-w[i]]+MOD)%MOD;//容斥一下
        }
    }
    for (register int i=1;i<=n;++i){
        for (register int j=1;j<=m;++j){
            putchar(ans[i][j]+'0');
        }
        puts("");
    }
}