容斥计数入门

常见公式：

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

一些常见的二项式反演：

\(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\)

如果 \(f,g\) 的维度很多的话那就对每一个维度都这么拆就行了（比如说后面 bzoj4487)

如果说 \(g\) 非常好求或者 \(f\) 的定义是 "正好" 的话就可以用普通的容斥原理搞来搞去了~

一些例题：

分特产 (luogu 5505)

共有 \(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; }

小w的喜糖 (BZOJ 4665 )

小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; }

毒瘤选举

有 \(n\) 个选民和 \(m\) 个候选人，每个选民只能投一张票，求有多少种方案使得每个候选人至少得到一张选票.

考虑容斥：令 \(f[k]\) 表示钦定 \(k\) 个候选人得不到选票的方案数，\(g[k]\) 表示恰好 \(k\) 个得不到选票的方案数.

那么有 \(f[k]=\binom{m}{k}\times (m-k)^n\)

而依据定义，\(f[k]=\sum_{i=k}^{m}\binom{i}{k}\times g[i]\)

二项式反演，得 \(g[k]=\sum_{i=k}^{m}(-1)^{i-k}\binom{i}{k}\times f[i]\)，带入求值即可.

原题的话模数是一个合数，但是可以被拆成若干个互不相同质数的乘积，需要用扩展CRT，这里就让模数是质数.

code:

#include <bits/stdc++.h> #define N 10005 #define LL long long using namespace std; void setIO(string s) { string in=s+".in"; freopen(in.c_str(),"r",stdin); } const LL mod=1000000007; LL fac[N],inv[N],f[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=0;i<=m;++i) f[i]=C(m,i)*qpow(m-i,n)%mod; LL ans=0ll; for(i=0;i<=m;++i) { LL d=(i&1)?-1:1; (ans+=(d*f[i]%mod+mod)%mod)%=mod; } printf("%lld\n",ans); return 0; }

染色问题 （BZOJ 4487）

给定 \(n\times m\) 的棋盘和 \(c\) 种颜色，要求对棋盘染色且每一行，每一列至少要被染上一种颜色，且 \(c\) 种颜色都要用上.

求方案数模 \(10^9+7\)

还是和以前一样，列 \(f_{i,j,k}\) 表示钦定 \(i\) 行 \(j\) 列未染色，\(k\) 种颜色未用上的方案数.

\(f_{i,j,k}=\binom{n}{i}\binom{m}{j}\binom{c}{k}(c-k+1)^{(n-i)(m-j)}\)

令 \(g_{i,j,k}\) 表示恰好的方案数，但是发现这个是 \(3\) 维的，而上面的都是二维的.

这里直接给出多维的容斥公式：

\(g_{i,j,k}=\sum_{x=i}^{n}\sum_{y=j}^{m}\sum_{l=k}^{c}(-1)^{l-k+x-i+y-j}\binom{l}{k}\binom{x}{i}\binom{y}{j}f_{x,y,l}\)

这里 \(i,j,k\) 都等于 \(0\)，直接套用即可.

code:

#include <bits/stdc++.h> #define N 504 #define LL long long #define setIO(s) freopen(s".in","r",stdin) using namespace std; const LL mod=1000000007; LL fac[N],inv[N],poww[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; } int main() { // setIO("input"); int n,m,c,i,j; scanf("%d%d%d",&n,&m,&c); fac[0]=inv[0]=1ll; for(i=1;i<N;++i) fac[i]=fac[i-1]*1ll*i%mod,inv[i]=Inv(fac[i]); LL ans=0ll; for(int k=0;k<=c;++k) { poww[0]=1ll; for(i=1;i<=n*m;++i) poww[i]=poww[i-1]*1ll*(c-k+1)%mod; for(i=0;i<=n;++i) for(j=0;j<=m;++j) { LL d=((i+j+k)&1)?-1:1; (ans+=(C(n,i)*C(m,j)%mod*C(c,k)%mod*poww[(n-i)*(m-j)]%mod*d+mod)%mod)%=mod; } } printf("%lld\n",ans); return 0; }

染色（luogu 4491)

给定长度为 \(n\) 的序列, 每个位置都可以被染成 \(m\) 种颜色中的某一种. 如果恰好出现了 \(s\) 次的颜色有 \(k\) 种, 则会产生 \(w_{k}\) 的价值. 求对于所有可能的染色方案，获得价值和对 \(1004535809\) 取模的结果.

设 \(lim=min(m,\frac{n}{s})\)，即最大可能的颜色出现种类. 按照套路，令 \(f[i]\) 表示钦定 \(i\) 种长度为 \(s\) 出现的方案数，\(g[i]\) 表示恰好 \(i\) 种出现的方案数.\(f[k]=\binom{m}{k}\frac{n!}{(n-ks)!(s!)^k}(m-k)^{n-ks}\) 组合意义就是选 \(ks\) 个位置放出现次数为 \(s\) 的颜色，然后其余部分随便放. 而 \(g[k]=\sum_{i=k}^{lim}\binom{i}{k}(-1)^{i-k}f[i]\) 因为我们要算贡献，所以要求 \(g[1]....g[lim]\) ，而上面的式子是 \(O(lim^2)\) 的. 考虑优化： 将上面 \(\binom{i}{k}\) 展开，得 \(g[k]=\frac{1}{k!}\sum_{i=k}^{lim} \frac{(-1)^{i-k}}{(i-k)!}f[i]\times i!\) 令 \(a[i]=\frac{(-1)^i}{i!}\)，\(b[i]=f[i]\times i!\) ，则 \(g[k]=\frac{1}{k!}\sum_{i=k}^{lim} a[i-k]\times b[i]\) 这是一个标准的卷积形式！ 直接用 NTT 加速即可.

#include <bits/stdc++.h> #define N 800005 #define LL long long #define setIO(s) freopen(s".in","r",stdin) using namespace std; const LL G=3; const LL mod=1004535809; LL A[N],B[N],Ct[N],f[N],g[N],fac[10000008],inv[10000007],val[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); } void NTT(LL *a,int n,int flag) { int i,j,k,mid; for(i=k=0;i<n;++i) { if(i>k) swap(a[i],a[k]); for(j=n>>1;(k^=j)<j;j>>=1); } for(mid=1;mid<n;mid<<=1) { LL wn=qpow(G,(mod-1)/(mid<<1)); if(flag==-1) wn=Inv(wn); for(i=0;i<n;i+=(mid<<1)) { LL w=1ll; for(j=0;j<mid;++j) { LL x=a[i+j],y=w*a[i+mid+j]%mod; a[i+j]=(x+y)%mod,a[i+j+mid]=(x-y+mod)%mod; w=w*wn%mod; } } } if(flag==-1) { LL re=Inv(n); for(i=0;i<n;++i) a[i]=a[i]*re%mod; } } LL C(int x,int y) { return fac[x]*inv[y]%mod*inv[x-y]%mod; } int main() { // setIO("input"); int n,m,s,i,j,lim; scanf("%d%d%d",&n,&m,&s); for(i=0;i<=m;++i) scanf("%lld",&val[i]); lim=min(m,n/s); inv[0]=fac[0]=1ll; int pp=max(n,m); for(i=1;i<=pp;++i) { fac[i]=fac[i-1]*1ll*i%mod; } inv[max(n,m)]=qpow(fac[max(n,m)],mod-2); for(i=max(n,m)-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod; for(i=0;i<=lim;++i) { f[i]=C(m,i)*fac[n]%mod*inv[n-i*s]%mod*qpow(inv[s],i)%mod*qpow(m-i,n-i*s)%mod*fac[i]%mod; } for(i=0;i<=lim;++i) A[i]=(inv[i]*(i&1?-1:1)+mod)%mod; for(i=0;i<=lim;++i) B[lim-i]=f[i]; LL ans=0ll; int tmp=1; while(tmp<=lim*2) tmp<<=1; NTT(A,tmp,1),NTT(B,tmp,1); for(i=0;i<tmp;++i) Ct[i]=A[i]*B[i]%mod; NTT(Ct,tmp,-1); for(i=0;i<=lim;++i) g[i]=Ct[lim-i]*inv[i]%mod; for(i=0;i<=lim;++i) { (ans+=g[i]*val[i]%mod)%=mod; } printf("%lld\n",ans); return 0; }