标签：sum 容斥 笔记 times 学习 bigcap Omega sim

目录

• 容斥原理

• 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] 硬币购物

题目链接：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