容斥原理小结

前言

其实我觉得,这篇博客更像是把__debug的课件搬过来了……即使真的像是把课件搬过来,我也想来写一写,算是给课件做一个更加详细的解释吧。(注:只要用了引用语法的,就是引用的__debug的原话)

经典容斥

先来看一下比较经典的容斥。经典的容斥总结起来,其实都是这样的一个问题:

给定一些条件,问全部满足的对象的个数。
答案 = 所有对象 - 至少不满足其中一个的 + 至少不满足其中两个的 - 至少不满足其中三个的 + …

相信对于基本的容斥,大家还是比较熟悉的。所以就直接上题了。

例题

懒癌犯了……放上以前的题解吧……

BZOJ2669 [CQOI2012]局部极小值

BZOJ4455 [ZJOI2016]小星星

总结

稍微总结一下,容斥原理在这里起到怎样的作用呢?大家可以感受一下:

  • $=$ 和 $\not=$
  • $\min$ 和 $\max$
  • $\gcd$ 和 $\mathrm{lcm}$
  • “恰好” 和 “至少”

凑系数

上面讲的,是比较经典的容斥。对于更加一般化的容斥,我们该怎么来定义呢?

对于更加一般的容斥,我们可以这样认为:
在所有物品中,问在某个条件$C_0$下所有物品的贡献之和。
构造一些相对容易计算贡献的条件$C_1,…,C_n$,再对于每个条件构造容斥系数$f_1,…,f_n$,满足对于每个物品
$$\sum_{i=1}^{n}s(C_i)f_i=s(C_0)$$
其中$s(C_i)$表示这个物品在条件$C_i$下所产生的贡献。
对于常见的计数问题,物品的贡献只会是$0/1$,表示这个物品是否满足此条件。

与我们之前常见的容斥相比较,这种容斥把容斥系数,条件的选择以及每个物品的贡献都一般化了。对于经典的容斥,容斥系数一般都形如$(-1)^k$,而$C_i$一般形如“给定了$n$个条件,满足了其中$i$个条件”,物品贡献也只会有$0/1$。

这种一般化的容斥该怎么理解呢?我们可以考虑我们最终容斥计数的时候是如何计算一个物品的贡献的。不难发现,等式右边是该物品应该产生的贡献,左边则是在对于每一个条件计算时产生的贡献。为了使我们最终计算出来的答案是正确的,我们必须配上一个容斥系数,使得这个式子对于所有物品都成立。

如果上面那个式子有所理解了,那么答案不难发现就是这样的式子:

$$\sum_{i=1}^{n}\sum_{T \in S}s(T,C_i)f_i$$

其中$S$为物品的集合,$s(T,C_i)$为物品$T$在条件$C_i$下产生的贡献。

这么理解有什么用呢?来看一个经典问题:

求长度为$n$的排列$a_1,…,a_n$的个数,满足$a_i \not= i$

构造$n$个条件,$C_i$表示有多少个物品,至少有$i$个位置满足$a_j=j$。对于任意一个恰好有$m$个位置满足$a_j=j$的排列,需要满足
$$\sum_{i=0}^{m}\binom{m}{i}f_i=[m=0]$$
容易看出$f_i=(-1)^i$

在这个问题里头,$s(C_i)$就不再是$0/1$了。由于$C_i$是有多少个物品,至少有$i$个位置满足$a_j=j$。考虑计算一个排列对$C_i$的贡献的时候,对于所有的$i$元组(每一个$i$元组的每一个元素均满足$a_j=j$),都会产生$1$的贡献。所以它对$C_i$的贡献$s(C_i)=\binom{m}{i}$。

可以得到,这个问题的答案即为$$\sum_{i=0}^{n}\binom{n}{i}(n-i)!(-1)^i$$

上式看似是可以通过普通容斥所得到的。但当我们将问题更加一般化,便能够体现出这种容斥的作用了。

定义每个排列的价值为$a_k$,其中$k$为这个排列的错排数。求所有排列的价值之和。

与上文的题目的解法是一模一样的,我们只要解出容斥系数$f_i$满足
$$\sum_{i=0}^{m}\binom{m}{i}f_i=a_m$$
那么答案就是
$$\sum_{i=0}^{n}\binom{n}{i}(n-i)!f_i$$
注意到这里的容斥系数,可以直接$O(n^2)$递推解决。当然有的题还需要打标找规律或者推一推式子。

例题

来看几个例题,加深一下对于这种容斥的理解。

“玲珑杯” 线上赛 Round 17 B

题意

给定$m$个数$a_1,…,a_m,$统计$[1,n]$的整数中,满足$a_1,…,a_m$中有奇数个数整除它的数的个数。

$T \le 1000,n \le 10^9,m \le 15$。

题解

首先,别像我一样想简单了……这题直接普通容斥肯定是错的……

显然解法肯定是枚举这$m$个数的子集,然后容斥。类似于上面错排那道题的构造方法,我们设$C_i$表示有多少个数被$k$个数整除。那么对于任意一个被$m$个数整除的数,显然有$$\sum_{i=0}^{m}\binom{m}{i}f_i=m \bmod 2$$

这个容斥系数可以打标找规律,当然$O(m^2)$递推也没有问题。至于求有多少个数被$k$个数整除,可以直接枚举集合,计算$\mathrm{lcm}$。

时间复杂度$O(T2^n)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=1e9;
const long double eps=1e-9;
const int maxm=20;
ll a[maxm+5],f[maxm+5];
inline ll read(){
ll x=0,flag=1;
char ch=getchar();
while(!isdigit(ch) && ch!='-')ch=getchar();
if(ch=='-')flag=-1,ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*flag;
}
int main(){
ll i,j,k,m,n,T;
T=read();
f[0]=0;f[1]=1;
for(i=2;i<=15;i++)f[i]=f[i-1]*(-2);
while(T--){
n=read();m=read();
for(i=1;i<=m;i++)a[i]=read();
ll ans=0;
for(i=1;i<(1<<m);i++){
ll Lcm=1;int cnt=0;
for(j=1;j<=m;j++){
if(!(i & (1<<(j-1))))continue;
Lcm=1ll*Lcm*a[j]/__gcd(Lcm,1ll*a[j]);
if(Lcm>n)break;cnt++;
}
ans+=(n/Lcm)*f[cnt];
}
printf("%lld\n",ans);
}
return 0;
}

BZOJ4671 异或图

题意

定义两个结点数相同的图$G_1$与$G_2$的异或为一个新的图$G$,其中如果$(u,v)$在$G_1$与$G_2$中的出现次数之和为$1$,那么边$(u,v)$在$G$中,否则这条边不在$G$中。

现在给定$s$个结点数均为$n$的图$G_1,…,G_s,$设$S=\{G_1,…,G_s\}$,求$S$有多少个子集的异或为一个连通图。

$n \le 10,s \le 60$。

题解

这道题并不太好做,看上去也没什么思路……感觉还是很巧妙的。我们设$f_i$为至少有$i$个联通块的方案数。考虑用贝尔数的时间来枚举子集划分,强制让划分出来的子集之间没有连边,子集内部的连边任意。那么满足条件的方案数,就要满足子集之间的连边异或起来一定是$0$的方案数。这时我们得到了许多个异或方程组。于是我们可以用线性基计算出线性无关的元素个数来得到对应的方案数。那么接下来,我们该怎么容斥呢?

我们设$C_i$表示至少有$i$个联通块的图的个数。对于任意一个有$m$个联通块的图,我们会对$C_i$产生$S(m,i)$的贡献。于是我们的容斥系数需要满足:
$$\sum_{i=1}^{m}S(m,i)f_i=[m=1]$$
可以打表找规律或者$O(n^2)$递推。当然还可以用斯特林反演来得到容斥系数,然而最后这一个窝不会……

得到了容斥系数,最后的答案也就是对于所有的子集划分,其方案数乘上对应的容斥系数的和了。时间复杂度$O(Bell(n)n^2s)$,上界很松,但稍微有点卡常数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=1e9;
const long double eps=1e-9;
const int maxn=10+5;
const int maxs=60+5;
char str[maxs][maxn*maxn];
int G[maxs][maxn][maxn],id[maxn],f[maxn];
struct node{
int x,y;
}a[maxn*maxn];
ll Base[maxs],ans=0;
int n,s;
inline int read(){
int x=0,flag=1;
char ch=getchar();
while(!isdigit(ch) && ch!='-')ch=getchar();
if(ch=='-')flag=-1,ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*flag;
}
void dfs(int cur,int lim){
int i,j,k;
if(cur>n){
memset(Base,0,sizeof(Base));
int cnt=0,pos=-1;
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
if(id[i]^id[j])a[++pos]=(node){i,j};
for(i=1;i<=s;i++){
ll val=0;
for(j=0;j<=pos;j++)if(G[i][a[j].x][a[j].y])val|=(1ll<<(1ll*j));
for(j=pos;j>=0;j--){
if(val & (1ll<<(1ll*j))){
if(!Base[j]){
Base[j]=val;cnt++;break;
}
else val^=Base[j];
}
}
}
ans+=f[lim]*(1ll<<(1ll*(s-cnt)));
return;
}
for(i=1;i<=lim+1;i++)id[cur]=i,dfs(cur+1,max(i,lim));
}
int main(){
int i,j,k,m;
#ifndef ONLINE_JUDGE
freopen("BZOJ4671.in","r",stdin);
freopen("BZOJ4671.out","w",stdout);
#endif
s=read();n=0;
for(i=1;i<=s;i++)scanf("%s",str[i]+1);
int len=strlen(str[1]+1);
while(n*(n-1)/2<len)n++;
for(i=1;i<=s;i++){
int cnt=0;
for(j=1;j<=n;j++)
for(k=j+1;k<=n;k++)
G[i][j][k]=str[i][++cnt]-'0';
}
f[1]=1;
for(i=2;i<=n+1;i++)f[i]=f[i-1]*(1-i);
dfs(1,0);
printf("%lld\n",ans);
return 0;
}

二项式反演

二项式反演主要有两个式子,同样是容斥原理的一种体现。

$$a_n=\sum_{i=0}^{n}\binom{n}{i}b_i \Rightarrow b_n=\sum_{i=0}^{n}(-1)^{n-i}\binom{n}{i}a_i$$
$$a_k=\sum_{i=k}^{n}\binom{i}{k}b_i \Rightarrow b_k=\sum_{i=k}^{n}(-1)^{i-k}\binom{i}{k}a_i$$

没有太多需要讲的,来道经典例题。

BZOJ3622 已经没有什么好害怕的了

题意

给两组$n$个数$a_1,…,a_n$,$b_1,…,b_n$,保证数字互不不相同。 问有多少种将它们配对的方式, 使得$b_i<a_i$的对数比$a_i<b_i$的对数多$k$。

$n \le 2000$。

题解

多$k$对显然可以转化为正好$k$对。但是正好$k$对似乎也不好做,于是我们再转化成至少$k$对。至少$k$对就会好做一些了。

将$a$数组排好序之后,可以想到一个这样的$dp$。设$dp[i][j]$表示$a$数组中前$i$个数能选出$j$对比$b$数组大的数。我们有这样的转移:
$$dp[i][j]=dp[i-1][j]+dp[i-1][j-1] \times (t_i-j+1)$$
其中$t_i$表示$a_i$比多少个$b$中的元素要大。此时不难理解为什么$a$数组之前要排好序了。

设$f_i$为至少有$i$对的方案数,$g_i$为恰好有$i$对的方案数。那么容易得到:
$$f_i=dp[n][i] \times (n-i)!$$
又因为
$$f_k=\sum_{i=k}^{n}\binom{i}{k}g_i$$
所以直接二项式反演就可以了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=1e9;
const long double eps=1e-9;
const int maxn=2e3+10;
const int mod=1e9+9;
int a[maxn],b[maxn],dp[maxn][maxn],cnt[maxn],C[maxn][maxn],fac[maxn],F[maxn];
inline int read(){
int x=0,flag=1;
char ch=getchar();
while(!isdigit(ch) && ch!='-')ch=getchar();
if(ch=='-')flag=-1,ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*flag;
}
inline void init(int n){
int i,j;
fac[0]=1;
for(i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
for(i=0;i<=n;i++){
C[i][0]=C[i][i]=1;
for(j=1;j<i;j++)
C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
}
int main(){
int i,j,k,m,n;
#ifndef ONLINE_JUDGE
freopen("BZOJ3622.in","r",stdin);
freopen("BZOJ3622.out","w",stdout);
#endif
n=read();k=read();if((n+k)%2==1)return puts("0"),0;
init(n);
k=(n+k)>>1;
for(i=1;i<=n;i++)a[i]=read();
for(i=1;i<=n;i++)b[i]=read();
sort(a+1,a+n+1),sort(b+1,b+n+1);
int pos=1;
for(i=1;i<=n;i++){
while(a[i]>b[pos] && pos<=n)pos++;
cnt[i]=pos-1;
}
dp[0][0]=1;
for(i=1;i<=n;i++)
for(j=0;j<=n;j++){
dp[i][j]=dp[i-1][j];
if(j)dp[i][j]=(dp[i][j]+1ll*dp[i-1][j-1]*max(0,cnt[i]-j+1))%mod;
}
for(i=1;i<=n;i++)F[i]=1ll*dp[n][i]*fac[n-i]%mod;
int ans=0;
for(i=k;i<=n;i++)(ans+=1ll*((i-k) & 1 ? -1 : 1)*C[i][k]*F[i]%mod)%=mod;
printf("%d\n",(ans+mod)%mod);
return 0;
}

后记

容斥原理个人认为应该算是组合计数中比较重要的内容。其中的一些技巧什么的这里并没有讲,只是稍微总结了一些经典的东西。有时间还是要学一学吧……

最后当然要orz __debug啦。