容斥

各种容斥。

本人水平有限，若有错误请务必提出。

理论知识

容斥原理

对于集合 $A_1,A_2,A_3,\dots,A_n$，

$$\left| \bigcup_{i = 1}^n A_i \right| = \sum_{\varnothing \neq S \subseteq \{1,2,\dots,n\}} (-1)^{|S| - 1} \left| \bigcap_{i \in S} A_i \right|$$

使用二项式定理计算一个元素在右边式子的出现次数可以证明上面公式。

推论：对于一个全集 $U$ 的子集 $A_1,A_2,A_3,\dots,A_n$，

$$\left| \bigcap_{i = 1}^n \overline A_i \right| = \sum_{S \subseteq \{1,2,\dots,n\}} (-1)^{|S|} \left| \bigcap_{i\in S} A_i \right|$$

这里 $\cap_{i \in \varnothing} A_i=U$。

证明：补集的交等于全集减去并集，并集使用第一个公式计算。

第一个公式的作用：或转化为全部；

第二个公式的作用：全都不转化为全部。

min-max 容斥

$$\max_{i = 1}^n a_i = \sum_{\varnothing \neq S \subseteq \{1,2,\dots,n\}} (-1)^{|S| - 1} \min_{i \in S} a_i$$

一个大概的证明：把 $x$ 看成 $(-\infty,x)$，则 $A \cup B = \max\{a,b\}$，$A \cap B = \min\{a,b\}$

看起来很没什么用，但重要的是这个式子对期望也成立。

对两个数的质因数质数进行 min-max 容斥可得：

$$\underset{i\in S}{\operatorname{lcm}}{x_i}=\prod_{T\subseteq S}{\left(\gcd_{j\in T}{x_j} \right)^{(-1)^{|T|-1}}}$$

二项式反演

先给出两个最常用的形式：

$$g(k) = \sum_{i = 0}^k \binom{k}{i} f(i) \Leftrightarrow f(k) = \sum_{i = 0}^k (-1)^{k - i} \binom{k}{i} g(i)$$

$$g(k) = \sum_{i = k}^n \binom{i}{k} f(i) \Leftrightarrow f(k) = \sum_{i = k}^n (-1)^{i - k} \binom{i}{k} g(i)$$

先来证明第一个形式。

证明当然可以用代数推导，这里给一个用上面容斥原理的方法。

假设全集 $U$ 中有 $n$ 个集合，其中任意若干个元素的并集、交集的大小仅与进行运算的集合个数有关，设 $g(x)$ 是任意 $x$ 个集合的交集，$f(x)$ 是任意 $x$ 个集合的并集，对所有集合的交集和所有集合补集的交集（并集）分别使用上面容斥原理的第二个公式可得：

$$g(n) = \sum_{i = 0}^n (-1)^i \binom{n}{i} f(i) \Leftrightarrow f(n) = \sum_{i = 0}^b (-1)^i \binom{n}{i} g(i)$$

设 $h(x) = (-1)^n g(x)$ 稍加整理即可得到上面的第一个形式。

后一个形式也可以用代数推导。

下面是反演两个形式对应的组合意义：

第一个形式：可以将“恰好 $k$ 个”转化为“除了 $k$ 个都不”，或者说“至多 $k$ 个”满足，即选取一些地方可以满足也可以不满足，其余地方一定不满足。

第二个形式：可以将“恰好 $k$ 个”转化为“选取 $k$ 个”，或者说“至少 $k$ 个”满足，即选取一些地方一定满足，其他无所谓。

实际运用中第二个形式较为常见。组合意义可以帮助理解二项式反演（或者说可以当成一个证明？）

莫比乌斯反演

也是一种容斥。

两个形式（这里不作证明）：

$$g(n) = \sum_{d \mid n}f(d) \Leftrightarrow f(n) = \sum_{d \mid n}\mu(d)g(\frac{n}{d})\\ g(n) = \sum_{k = 1}^\infty f(kn) \Leftrightarrow f(n) = \sum_{k = 1}^\infty \mu(k)g(kn)$$

一个是枚举约数，一个是枚举倍数，第一种形式还可以从狄雷克雷卷积的形式理解：$g = 1 * f \Leftrightarrow f = \mu * g$。

高维前缀和/差分

也许可以看作“子集反演”（同样不作证明）。

$$f(S) = \sum_{T \subseteq S}g(T) \Leftrightarrow g(S) = \sum_{T \subseteq S}(-1)^{|S| - |T|}f(S)$$

左半部分是高维前缀和，那么后半部分就是其逆运算，即高维差分。计算时候无需枚举子集计算，使用 FMT，复杂度 $O(n2^n)$。

当然如果把公式里每个集合取补集，那也可以变成“超集反演”。

例题

loj3119 CTS2019 随机立方体

链接

首先把恰好 $k$ 个用二项式反演变为选取 $k$ 个。很显然任意两个极大点都不会共面，那么选取 $k$ 个点的方案数就是 $n^{\underline k}m^{\underline k}l^{\underline k}$。

设有 $i$ 个极大值，被限制住的点数是 $f_i=nml-(n-i)(m-i)(l-i)$。

选取一些点被极大值限制的方案数是 $\binom{nml}{f_i}$ 剩下的点可以随便排，就是再乘一个 $(n-k)(m-k)(l-k)!$ 都是显然的。

然后考虑有限制内部怎么算，设 $i$ 个极大值的方案数是 $g_i$，我们从小到大加入极大值，可以写出递推式：$g_i=g_{i - 1} \times \dfrac{(f_i - 1)!}{f_{i - 1}!}$，算一下可以解出来 $g_i=f_i!\prod_{j = 1}^i \dfrac{1}{f_j}$。

这里还有一个巧妙的计算方法：考虑树的拓扑序，一个有 $n$ 个点的有根树的拓扑序怎么求呢？其充要条件是：对于每个 $i$，$i$ 子树中的点都出现在其后面，子树之间是独立的，故总方案数为：$n!\prod_{i = 1}^n \dfrac{1}{siz_i}$。回到原题，我们发现把一个点连向需要比其大的点就可以转化为一个树上的拓扑序模型，可以直接得到答案。

以上都乘起来，再除以总方案数，得到 $n^{\underline k}m^{\underline k}l^{\underline k}\prod_{j = 1}^k \dfrac{1}{f_j}$，最后再反演一下即可。

复杂度线性或者带一个快速幂的 $\log p$

CF990G GCD Counting

链接

把 $k = g(x, y)$ 用上面莫比乌斯反演的第二个形式变为 $k \mid g(x, y)$，就很好做了。只需要对于每个约数，把点权是其倍数的点加入图中，算出所有连通块大小，一个连通块的贡献就是 $siz * (siz + 1) / 2$。

uoj422 小Z的礼物

直接使用min-max容斥：

$$ans = \sum_{\varnothing \neq T \subseteq S} (-1)^{|T| - 1}\frac{all}{cnt_T}$$

$S$ 是所有喜欢物品的集合，$all$ 指的是所有相邻格子的数量，$cnt_T$ 是对于一个喜欢的物品集合，有多少种选法能至少一个选到喜欢的物品。

直接枚举子集是不能接受的，我们把 $cnt_T$ 放到状态里，容斥的系数当成 dp 的值，使用插头dp（轮廓线dp），时间复杂度 $O(n^2m^22^n)$。

agc028d Chords

链接

圆没有用，直接变成一个链，两条弦有交叉则在同一个连通块内。

考虑求出每个连通块在所有方案中的出现次数来计算贡献，使用（最小值，最大值）来代表一个连通块。注意到 $[l,r]$ 代表的连通块在 $[l+1,r-1]$ 不能有边向外连，这是很好的性质。

设 $g(n)=(n-1)\times (n-3)\times …\times 3\times 1$ 表示 $n$ 个点内部随便连的方案数（$n$ 是偶数则方案数为 $0$）。$f_{i, j}$ 表示 $[i,j]$ 在同一个连通块内，且中间的点没有向外连边的方案数。中间的点没有向外连边是好满足的，对于在同一个连通块内的要求，使用容斥原理，用所有的减去 $[i,j]$ 不在同一个连通块内的。

$$f_{i,j}=g(cnt1) - \sum\limits_{k = i}^{j - 1}f_{i,k}\times g(cnt2)\\ ans=\sum f_{i,j}\times g(n - 2K - cnt)$$

$cnt$ 表示区间内可以自由连边的点数。

agc036f Square Constriants

链接

预处理出上界 $L_i\leq p_i < R_i$，对于 $i\geq n$，$L_i=0$。

没有下界的情况是简单的，按照上界排序后，$ans=\prod_{0\leq i <2n} (R_i-i)$。

不知道为什么（是因为不满足条件的是一段前缀吗）考虑容斥原理。

枚举有下界的有几个不满足限制（即上界为 $L_i-1$），$ans=\sum_{i = 0}^n (-1)^i f(i)$

对于小于 $n$ 的数排序关键字为 $(L_i,R_i)$，其余的为 $(R_i,0)$ 排序。

然后设 $f_{i,j}$ 表示前 $i$ 个数，选了 $j$ 个取下界为上界的方案数，转移的时候考虑有几个数排序后在这个数的前面转移。因为对于 $i<n$，最大的 $L$ 比最小的 $R$ 要小，因此转移的时候是可以排出顺序的。

loj2026 成绩比较

见单独题解： loj2026 JLOI/SHOI2016 成绩比较