容斥计数入门

常见公式：

先给出几个重要的公式/结论：

一些常见的二项式反演：

\(f_n=\sum_{i=0}^{n}(-1)^i\binom{n}{i}g_i\Rightarrow g_n=\sum_{i=0}^{n}(-1)^i\binom{n}{i}f_i\)

\(f_{n}=\sum_{i=0}^{n}\binom{n}{i}g_i\Rightarrow \sum_{i=0}^{n}(-1)^{n-i}\binom{n}{i}f_i\)

\(f_{k}=\sum_{i=k}^{n}(-1)^i\binom{i}{k}g_i\Rightarrow g_k= \sum_{i=k}^{n}(-1)^i\binom{i}{k}f_i\)

\(f_{k}=\sum_{i=k}^{n}\binom{i}{k}g_i\Rightarrow g_k=\sum_{i=k}^{n}(-1)^{i-k}\binom{i}{k}f_i\)

证明什么的就先略过了~

广义容斥原理：

设全集元素个数为 \(n\)，\(f(i)\) 表示钦定 \(i\) 个为一组，其余 \(n-i\) 个元素随便弄得方案数，\(g(i)\) 表示恰好有 \(i\) 个发生的方案数. （可以去看分特产）

则有 \(f(k)=\sum_{i=k}^{n}\binom{i}{k}g(i)\)

这是上面二项式反演的一种形式，直接反演，得:

\(g_k=\sum_{i=k}^{n}(-1)^{i-k}\binom{i}{k}f_i\)

所以，知道 \(f\) 的情况下可以用二项式反演求 \(g\)

一些例题：

luogu 5505 [JSOI2011]分特产

共有 \(m\) 种物品，每个物品 \(a[i]\) 个，分给 \(n\) 个人，每个人至少要拿到一件，求方案数.

令 \(f[i]\) 表示钦定 \(i\) 个没分到特产，其余 \((n-i)\) 个人随便选的方案数，\(g[i]\) 表示恰好 \(i\) 个没分到特产的方案数.

按照我们之前讲的，有 \(f[k]=\sum_{i=k}^{n}\binom{k}{i}g[i]\Rightarrow g[k]=\sum_{i=k}^{n}(-1)^{i-k}\binom{i}{k}f[i]\)

而根据定义，\(f[i]=\binom{n}{i}\times \prod_{j=1}^{m}\binom{a[j]+n-i-1}{n-i-1}\)

所以先预处理 \(f[i]\)，然后求 \(g[0]\) 就好了（恰好 \(0\) 个人没分到特产的方案数）

code:

#include <bits/stdc++.h>
#define N 10005
#define LL long long
using namespace std;
const LL mod=1000000007;
void setIO(string s)
{
    string in=s+".in";
    string out=s+".out";
    freopen(in.c_str(),"r",stdin);
}
int a[N];
LL fac[N],inv[N],f[N],g[N];
LL qpow(LL x,LL y)
{
    LL tmp=1ll;
    for(;y;y>>=1,x=x*x%mod)
        if(y&1) tmp=tmp*x%mod;
    return tmp;
}
LL Inv(LL x) { return qpow(x,mod-2); }
LL C(int x,int y)
{
    return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
int main()
{
    // setIO("input");
    int i,j,n,m;
    fac[0]=inv[0]=1ll;
    for(i=1;i<N;++i) fac[i]=fac[i-1]*1ll*i%mod,inv[i]=Inv(fac[i]);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i) scanf("%d",&a[i]);
    for(i=0;i<=n;++i)
    {
        f[i]=C(n,i);
        for(j=1;j<=m;++j) (f[i]=f[i]*C(a[j]+n-i-1,n-i-1)%mod)%=mod;
    }
    for(i=0;i<=n;++i)
    {
        (g[0]+=qpow(-1,i)*f[i]%mod+mod)%=mod;
    }
    printf("%lld\n",g[0]);
    return 0;
}   

BZOJ 2839: 集合计数

在一个 \(N\) 个元素集合中的所有子集中选择若干个，且交集大小为 \(k\) 的方案数.

按照之前的套路，令 \(f[k]\) 表示钦定交集大小为 \(k\)，其余随便选的方案数. 令 \(g[k]\) 表示交集恰好为 \(k\) 的方案数.
则有 \(f[k]=\sum_{i=k}^{n}\binom{i}{k}g[k]\)，反演得 \(g[k]=\sum_{i=k}^{n}(-1)^{i-k}\binom{i}{k}f[i]\)
而 \(f[k]=\binom{n}{k}2^{2^{n-k}}\)，直接带入求值即可.

code:

#include <bits/stdc++.h>
#define N 1000005
#define LL long long
using namespace std;
const LL mod=1000000007;
void setIO(string s)
{
    string in=s+".in";
    string out=s+".out";
    freopen(in.c_str(),"r",stdin);
}
int a[N];
LL fac[N],inv[N],f[N],g[N],poww[N];
LL qpow(LL x,LL y)
{
    LL tmp=1ll;
    for(;y;y>>=1,x=x*x%mod)
        if(y&1) tmp=tmp*x%mod;
    return tmp;
}
LL Inv(LL x) { return qpow(x,mod-2); }
LL C(int x,int y)
{
    return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
int main()
{
    // setIO("input");
    int i,j,n,k;
    fac[0]=inv[0]=poww[0]=1ll;
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;++i)
        fac[i]=fac[i-1]*1ll*i%mod,inv[i]=Inv(fac[i]),poww[i]=poww[i-1]*2ll%(mod-1);
    for(i=0;i<=n;++i)
        f[i]=C(n,i)*qpow(2,poww[n-i])%mod;
    LL ans=0ll;
    for(i=k;i<=n;++i)
        (ans+=(qpow(-1,i-k)*C(i,k)%mod*f[i]%mod+mod)%mod)%=mod;
    printf("%lld\n",ans);
    return 0;
} 

BZOJ 4665 小w的喜糖

小w一共买了 \(n\) 块喜糖，发给了 \(n\) 个人，每个喜糖有一个种类。这时，小w突发奇想，如果这n个人相互交换手中的糖，那会有多少种方案使得每个人手中的糖的种类都与原来不同。

还是考虑容斥：为了方便，我们将同一种糖果也依次编号，这样在计算时候会简便一些.

令 \(f[i][j]\) 表示考虑前 \(i\) 种糖果，\(j\) 个人拿到同种糖果的方案数.

则有转移：\(f[i][j]=\sum_{k=0}^{min(j,cnt[i])}f[i-1][j-k]\times \binom{cnt[i]}{k} \times A_{cnt[i]}^{k}\)

考虑这个转移的组合意义：我们在 \(i\) 糖果中强制选择 \(k\) 个人拿同样的糖果，为 \(\binom{cnt[i]}{k}\)

而每一个人分别有：\(cnt[i],cnt[i]-1,......\) 种选择，即总共是 \(A_{cnt[i]}^{k}\) 种选糖方案（编号不同）

那么选择人的方案 $\times $ 选择糖的方案 = \(i\) 种糖中选择 \(k\) 个人，每个人都拿自己种类的方案数.

得到 \(f[n][i]\) 后，让其他 \((n-i)\) 个人随便选，即 \(f[n][i]\times (n-i)!\Rightarrow f[n][i]\)

推出 \(f[n][i]\) 后就简单了（这个组合意义是强制让 \(i\) 个人拿到自己糖的组合方案）

直接上二项式反演，得 \(g[0]=\sum_{i=0}^{n}(-1)^i\times f[n][i]\)
别忘了，最后还有除一下阶乘，因为我们把每个糖得不同编号也看作不同了~

code:

#include <bits/stdc++.h>
#define N 2005
#define LL long long
using namespace std;
const LL mod=1000000009;
void setIO(string s)
{
    string in=s+".in";
    freopen(in.c_str(),"r",stdin);
}
int cnt[N],sum[N];
LL fac[N],inv[N],f[N][N];
LL qpow(LL x,LL y)
{
    LL tmp=1ll;
    for(;y;y>>=1,x=x*x%mod)
        if(y&1)  tmp=tmp*x%mod;
    return tmp;
}
LL Inv(LL x) { return qpow(x,mod-2); }
LL C(int x,int y) { return fac[x]*inv[y]%mod*inv[x-y]%mod; }
LL A(int x,int y) { return fac[x]*inv[x-y]%mod; }
int main()
{
    // setIO("input");
    int i,j,n,k;
    scanf("%d",&n);
    fac[0]=inv[0]=1ll;
    for(i=1;i<=n;++i) fac[i]=fac[i-1]*1ll*i%mod,inv[i]=qpow(fac[i],mod-2);
    for(i=1;i<=n;++i)
    {
        int x;
        scanf("%d",&x),++cnt[x];
    }
    for(i=1;i<=n;++i) sum[i]=sum[i-1]+cnt[i];
    f[0][0]=1ll;
    for(i=1;i<=n;++i)
    {
        for(j=0;j<=sum[i];++j)
        {
            for(k=0;k<=min(cnt[i],j);++k)
                (f[i][j]+=f[i-1][j-k]*C(cnt[i],k)%mod*A(cnt[i],k)%mod)%=mod;
        }
    }
    LL ans=0ll;
    for(i=0;i<=n;++i)
    {
        LL d=(i&1)?-1:1;
        (ans+=(d*f[n][i]%mod+mod)*fac[n-i]%mod)%=mod;
    }
    for(i=1;i<=n;++i) ans=ans*inv[cnt[i]]%mod;
    printf("%lld\n",ans);
    return 0;
}