目录
-
容斥原理
-
Min-Max 容斥
-
广义容斥原理
容斥原理
原理:
\[|\bigcup_{i=1}^nA_i|=\sum_{j=1}^n(-1)^{j-1}\sum_{a_k\not=a_ {k+1}}\bigcap_{l=1}^mA_{a_i}\]这东西学过小学奥数就会了。
一些有用的结论:
\[|\bigcap_{i=1}^nA_i|=|\Omega| - |\bigcup_{i=1}^n\overline{A_i}| \]应用
错排
问题: 求出大小为 \(n\) 的排列的错排数。
思路:
很明显可以用 \(D_n=(n-1)(D_{n-1}+D_{n-2})\) 来做,但是其实也可以容斥。
\(S_i\):\(P_i\not= i\) 的排列集合。
答案即为:\(|\bigcap_{i=1}^nS_i|\)。
根据结论:
\[\begin{aligned} |\bigcap_{i=1}^nS_i| &=|\Omega|-|\bigcup_{i=1}^n\overline{S_i}|\\ &=|\Omega|-\sum_{m=1}^n(-1)^{m-1}\sum_{a_1 \sim a_m}|\bigcap_{i=1}^m\overline{S_{a_i}}| \end{aligned} \]而 \(S\) 的补集就是 \(P_i = i\) 的排列,相当于有 \(m\) 个位置确定了,所以:
\[\begin{aligned} |\Omega|-\sum_{m=1}^n(-1)^{m-1}\sum_{a_1 \sim a_m}|\bigcap_{i=1}^n\overline{S_{a_i}}| &=|\Omega|-\sum_{m=1}^n(-1)^{m-1}\binom{n}{m}(n-m)!\\ &=|\Omega|-\sum_{m=1}^n(-1)^{m-1}\frac{n!}{m!}\\ &=n!-n!\sum_{m=1}^n(-1)^{m-1}\frac{1}{m!}\\ &=n!\sum_{m=0}^n\frac{(-1)^m}{m!}\\ \end{aligned} \]这样就得到了 \(D_n\) 的通项公式,可以证明这个数趋近于 \(\frac{1}{e}\)。
第二类斯特林数
问题: 求第二类斯特林数 \(n,k\),即 \(n\) 个球放入 \(k\) 个盒子,盒子无顺序,盒子非空。
思路:
同样,也有递推公式,但是也可以容斥。
首先,假定盒子有顺序,最后除以 \(k!\) 即可。
\(S_i\):第 \(i\) 个盒子非空的方案。
答案即为:\(|\bigcap_{i=1}^nS_i|\)。
同理,转化成求:
\[|\Omega|-\sum_{m=1}^k(-1)^{m-1}\sum_{a_1 \sim a_m}|\bigcap_{i=1}^m\overline{S_{a_i}}| \]现在考虑有 \(m\) 个盒子一定为空,则每个球都只有 \((k-m)\) 中选择,总共有 \((k-m)^n\) 种。
经过推导就可以得到:
\[|\Omega|-\sum_{m=1}^k(-1)^{m-1}\binom{k}{m}(k-m)^n \]又因为 \(|\Omega|=k^n\),所以答案即为:
\[\sum_{m=0}^k(-1)^m\frac{(k-m)^{(n-1)}}{m!} \]欧拉函数
问题: 求欧拉函数 \(\varphi(n)\)。
思路:
设 \(n = \prod_{i=1}^kp_i\)。
\(S_i\):不被 \(p_i\) 整除的数。
答案即为:\(|\bigcap_{i=1}^nS_i|\)。
同理,转化成求:
\[|\Omega|-\sum_{m=1}^k(-1)^{m-1}\sum_{a_1 \sim a_m}|\bigcap_{i=1}^m\overline{S_{a_i}}| \]现在要求的即是被 \(p_{a_1}p_{a_2}\dots p_{a_m}\) 整除的数的个数,即:\(\frac{n}{p_{a_1}p_{a_2}\dots p_{a_m}}\)。
所以可以变为:
\[n(\sum_{m=0}^n(-1)^m\sum_{a_1 \sim a_m}\frac{1}{\prod_{i=1}^mp_{a_i}}) \]这个其实就是 \(n\prod_{i=1}^k(1-\frac{1}{p_i})\) 的展开。
不定方程
问题: 求不定方程 \(\sum_{i=1}^nx_i=m\) 的非负解的个数,要求 \(x_i \le b_i\)。
思路:
首先,如果没有性质,那就是经典问题,挡板法可知答案为 \(\binom{n+m-1}{n}\)。
于是依然考虑容斥。
\(S_i\):\(x_i \le b_i\) 的方案。
答案即为:\(|\bigcap_{i=1}^nS_i|\)。
同理,转化成求:
\[\sum_{a_1 \sim a_m}|\bigcap_{i=1}^m\overline{S_{a_i}}| \]现在就是要求 \(x_{a_i} \le b_{a_i}+1\)
而我们可以先给所有的 \(x_{a_i}\) 减去 \(b_{a_i}+1\),然后就成了没有限制的挡板法,可以直接计算。
然后就做完了。
互素数对
问题: \(n\) 个数 \(a_1 \sim a_n\),求数对 \((i,j)\) 个数,要求 \(a_i, a_j\) 互素。\(n \le 10^5, a_i \le 10^6\)。
思路:
容斥。
设 \(p_1 \sim p_k\) 为 \(10^6\) 以内的素数。
\(S_i\):所有都能整除 \(p_i\) 的数对。
答案即为:
\[n^2 - \sum_{m=1}^k(-1)^{m-1}\sum_{a_1 \sim a_m}|\bigcap_{i=1}^mS_{a_i}| \]考虑到都在 \(10^6\) 以内,预处理出每个 \(x\) 的倍数个数,暴力搜索即可。
P1450 [HAOI2008] 硬币购物
思路:
这道题的重点在于如何转换为容斥原理,我们把每一种使得最终和为 \(s\) 的方案(没有数量限制)看作一个元素,则假设有所有方案的集合为 \(S\),而方案中第 \(i\) 种硬币数量超出 \(d_i\) 的所有方案的集合为 \(A_i\),则我们需要求的答案其实就是:
\[|S|-|\bigcup_{i=1}^4A_i| \]那么该如何的去求出 \(|S|\) 与 \(|\bigcup_{i=1}^4A_i|\) 呢?
首先我们设 \(dp_i\) 表示硬币数量不受限制,最终和为 \(i\) 的方法数,这很明显是一个完全背包,由于题目中 \(s \le 10^5\) ,所以直接预处理即可,这样 \(|S|\) 就是 \(dp_s\)。
void init() {
dp[0] = 1;
for (int i = 1; i <= 4; i++) {
for (int j = c[i]; j <= 100000; j++)
dp[j] += dp[j - c[i]];
}
}
考虑如何求 \(|A_i|\),我们可以先取 \(d_i+1\) 个 \(i\) 种硬币,那么还剩下 \(s-(d_i+1) \times c_i\) 的金额,再怎么取 \(i\) 的数量肯定超出限制,于是方法数即为 \(dp_{s-(d_i+1) \times c_i}\),然后就求出了 \(|A_i|\)
同理,如果 \(i\) 与 \(j\) 都超出了限制,你们方法数也应该为 \(dp_{s-(d_i + 1) \times c_i - (d_j+1) \times c_j}\) ,三个或四个的以此类推。
这很明显是一个容斥,于是直接根据容斥原理算,只用枚举每次是哪几类超出限制即可,复杂度 \(O(2^4n)=O(16n)=O(n)\)。
如果这题物品种类有 \(m\) 个,复杂度就是 \(O(n2^m)\)。
P5505 [JSOI2011]分特产
题目链接:P5505 [JSOI2011]分特产
思路:
这道题的重点以人为单位来计数。
首先说一下可重组合,即把 \(n\) 分成 \(m\) 个非负整数集合,它们的和为 \(n\) 的方法数,我们用小学奥数的挡板法即可得到答案是:\(C_{n+(m-1)}^{m-1}\)。
我们设 \(T_{i,k}\) 表示把第 \(i\) 种特产,数量为 \(a_i\),分给 \(k\) 个人的方法数(不一定每个人都要分到)。这个问题和上面其实是同一个问题,所以 \(T_{i,k}=C_{a_i+(k-1)}^{k-1}\)。
设 \(N_k\) 为把所有特产分给 \(k\) 个人的方法数(依然有人可能没拿到),因为每个特产都要被分发,且第 \(i\) 种特产分给 \(n\) 个人的方法数是 \(T_{i,n}\),所以这是一个乘法原理,即:
\[N_k=\prod_{i=1}^mT_{i,k} \]设集合 \(A_i\) 为第 \(i\) 名同学没有被分到特产的所有方案的集合,\(S\) 为所有人分所有特产(有人可以没分到)的方案的集合,因为我们要保证每个人都被分到,所以我们要求的就是:\(|S|-|\bigcup\limits_{i=1}^nA_i|\)。
很明显 \(|S| = N_n\),考虑如何求 \(|\bigcup\limits_{i=1}^nA_i|\)。我们先考虑如果某一个同学没拿到特产的方法数(别的也不一定都拿到)应该为 \(N_{n-1}\),因为有 \(n\) 个人,所以总共是: \(C_n^1 \times N_{n-1}\)。在考虑有两个人没拿到特产的方法数,总共应该是 \(C_n^2 \times N_{n-2}\),而上面这两者是有交集的,于是根据容斥原理,我们可以以此类推,得到:
\[|\bigcup\limits_{i=1}^nA_i|=\sum_{i=1}^n(-1)^{i+1}C_n^i\times N_{n-i} \]所以答案其实就是:
\[\sum_{i=0}^n(-1)^{i}C_n^i\times N_{n-i} \]然后就快乐的 AC 了~~
P6076 [JSOI2015]染色问题
题目链接:P6076 [JSOI2015]染色问题
思路:
设 \(T_i\) 为有 \(i\) 种颜色确定不用,剩下的颜色随意的方法数,则根据容斥原理,我们要求的就是:
\[\sum_{i=0}^n(-1)^i\times C_n^i \times T_i \]考虑如何求 \(T_k\)。我们记 \(N_i\) 为有 \(i\) 行确定不涂色,其他行随意的,但是每一列都有颜色的方法数,则根据容斥原理,很明显:
\[T_k = \sum_{i=0}^n(-1)^i\times C_n^i\times N_i \]考虑如何求 \(N_i\)(别烦,这时最后一个了)。我们考虑把每一列拆开来,因为每一列有 \(n-i\) 个格子需要染色,每个格子有 \(c-k+1\) 种染色方法(不染色也算一种),所以对于一列来说,共有 \((c-k+1)^{n-i}\) 种染色方式,但是不能全部不染色,所以还要减去一,即 \((c-k+1)^{n-i}-1\)。因为总共有 \(m\) 列,并且每一列是相互独立的,于是就知道了:
\[N_i = [(c-k+1)^{n-i}-1]^m \]然后就可以求出 \(T_k\),最后求出答案了。
在具体实现中,其实并不需要去真的开三个数组。这题除了求组合数时阶乘以及逆元需要开个数组,其他都没必要。
代码很简单,但其实思维难度还是很高的。
Min-max 容斥
公式:
\[\max_{i \in S}x_i=\sum_{T \subset S,T \not = \emptyset}(-1)^{|T|-1}\min_{j \in T}x_j \]\[\min_{i \in S}x_i=\sum_{T \subset S,T \not = \emptyset}(-1)^{|T|-1}\max_{j \in T}x_j \]证明:
定义 \(f(n)=\{x|1 \le x \le n, x \in \mathbb{Z}\}\),则 \(f(\max(x,y))=f(x) \bigcup f(y)\),\(f(\min(x,y))=f(x) \bigcap f(y)\)。
于是上面的式子和容斥原理其实是等价的。
应用
首先这东西看上去没啥用,但是它最重要的是对期望也成立:
\[E(\max_{i \in S}x_i)=\sum_{T \subset S,T \not = \emptyset}(-1)^{|T|-1}E(\min_{j \in T}x_j) \]于是这就可以解决一些期望问题。
题目1: 【Card Collector】hdu-4336
题目2: 【随机游走 (PKUWC’18)】loj-2542
广义容斥原理
全集 \(\Omega\) 中有若干个元素,有 \(n\) 种性质,\(A_i\) 表示满足第 \(i\) 个性质的元素的集合。
设 \(\beta_k\) 表示恰好满足 \(k\) 中性质的元素集合。
定义 \(\alpha_k=\sum_{i_1 < i_2 < \dots < i_k}|A_{i_1} \cap A_{i_2} \cap \dots \cap A_{i_k}|\)。
则 \(\alpha_k = \sum_{i=k}^n \binom{i}{k}\beta_i\)。
理解:
我们考虑实际满足了 \(i\) 种性质的元素在 \(\alpha_k\) 中被算了 \(\binom{i}{k}\) 次,所以这个式子成立。
作用:
根据二项式反演公式3(见二项式反演学习笔记),如果 \(\alpha_k\) 好算,那么我们我们可以反演用 \(\alpha_k\) 求出 \(\beta_k\)。
题目1: 有两个序列 \(a_1 \sim a_n\) 与 \(b_1 \sim b_n\),数字各不相同,求匹配方案数,使得 \(a_i > b_{p_i}\) 的个数恰好为 \(k\)。\(n \le 5000\)(P4859 已经没有什么好害怕的了)
思路:
我们让性质 \(i\) 表示 \(a_i > b_{p_i}\),则我们要求的就是 \(\beta_k\),根据广义容斥原理,我们如果能求出 \(\alpha_k\) 就能解决问题。
考虑如何求 \(\alpha_k\)。数据范围支持 \(O(n^2)\),考虑 dp。
首先需要对两个数组排序。
不妨设 \(f[i][j]\) 表示前 \(i\) 个 \(a\) 中匹配了 \(j\) 个使得满足 \(a_i > b_{p_i}\),所以 \(\alpha_k = (n-k)!f[n][k]\)。
考虑递推,按照第 \(i\) 个分类,可得到 \(f[i][j] = f[i - 1][j] + (cnt[i] - j + 1)f[i - 1][j - 1]\),\(cnt[i]\) 表示有多少个 \(b\) 小于了 \(a_i\)。
第一项好理解,第二项就是 \(i\) 要满足性质,则有 \(cnt[i]\) 个选择,但是前面已经占了 \(j-1\) 个,所以总共只有 \(cnt[i] - (j-1)= cnt[i]-j+1\) 种。
然后就能解决这道问题了。
标签:sum,容斥,笔记,times,学习,bigcap,Omega,sim From: https://www.cnblogs.com/rlc202204/p/17976394