一些容斥原理
规定
本文中集合指代非可重集。
用大写字母记一个集合，例如 \(P, S\)。
在集合两侧加竖线表示集合的大小，例如 \(\left\lvert\{1,2,3,4,5\}\right\rvert = 5\)。
在有上下文信息的情况下，直接写出集合也可以表示该集合对应的一类贡献，其与集合内元素线性相关。
下文中在描述下标集合时常会看到 \(S, T\) 这两个用于枚举的中间量集合，这里记 \(S\) 表示下标全集，\(T\) 表示当前枚举到的 \(S\) 的一个子集。
规定 \(0^0 = 1\)，这也是有实际意义的。
容斥原理
就是最普适的容斥原理了。我们需要计算一系列集合的并，但又不希望重叠部分的贡献计入多次，这时就需要通过多次计数，每次[把先前没有计算的部分容纳进来/把先前重复计算的部分排斥出去]，定量地加以容斥系数来实现不重不漏的计数，这样的做法就叫容斥原理。
假设我们需要计数集合列 \(\langle P_n \rangle\) 的贡献，容易得到
\[\bigcup_{i \in S} P_i = \sum_{T\subseteq S} (-1)^{\lvert T\rvert - 1} \bigcap_{j \in T} P_j \]该式子描述了容斥原理的核心，其他的容斥可以说都是从这个式子上衍生的。
证明也是比较方便的。考虑一个元素在集合列中的 \(m\) 个集合中出现，则可以发现，选择 \(k\) 个其出现的集合有 \(C_m^k\) 种可能，每种可能的系数是 \((-1)^{k - 1}\)。最后能写出
\[\sum_{i = 1}^m (-1)^{i - 1} \binom{m}{i} = \binom{m}{0} - (1 - 1)^m = 1 \]也可以通过归纳法证明。
集合的交的问题可以转化成集合的并来解决，就是全集减去补集的并。
\(\text{Min-Max}\) 容斥
对于一个元素之间满足全序关系且有加减性的元素列 \(\{x_i\}\)，设其大小为 \(n\)，则我们有以下关系：
\[\max_{i\in S} x_i = \sum_{T\subseteq S} (-1)^{\lvert T\rvert - 1} \min_{j\in T} x_j \]\[\min_{i\in S} x_i = \sum_{T\subseteq S} (-1)^{\lvert T\rvert - 1} \max_{j\in T} x_j \]证明就是讨论元素贡献。取 \(m\in S\)，假设 \(x_m\) 是第 \(k\) 大的元素，则可以讨论 \(x_k\) 会作为哪些集合的元素出现。
- \(k = 1\)
我们需要的就是 \(x_m\)，容易发现它只会在 \(\{x_m\}\) 这一个集合中作为最小值出现。
所以它的贡献就是 \((-1)^{0} x_m = x_m\)。 - \(k\ge 1\)
最小的元素是第 \(k\) 大的元素，那其余元素只能是第 \(l < k\) 大的元素了，这样的元素一共有 \(k - 1\) 个。
可以写出选择 \(i + 1\) 个的贡献系数，也就是\[\sum_{i = 0}^{k - 1} \binom{k - 1}{i} (-1)^{i - 1} = (1 - 1)^{k - 1} = 0 \]
因此最后的贡献是第一小的数，即 \(\max_{i\in S} x_i\)。最小值可以如上地证明。
因此得证。
\(\text{Min-Max}\) 容斥之所以有用，其中一个原因是它在期望上也成立：众所周知在期望意义下的 \(\max, \min\) 是不像普通的 \(\max, \min\) 那么好求的，需要做转化。写出式子：
\[E\left(\max_{i\in S} x_i\right) = \sum_{T\subseteq S} (-1)^{\lvert T\rvert - 1} E\left(\min_{j\in T} x_j\right) \]\[E\left(\min_{i\in S} x_i\right) = \sum_{T\subseteq S} (-1)^{\lvert T\rvert - 1} E\left(\max_{j\in T} x_j\right) \]证明：
可以通过枚举可能的 \(y\) 序列写出一种期望的表示方法：
\[E\left(\max_{i\in S} x_i\right) = \sum_{y} P(y = x) \max_{j\in S} y_j \]可以发现后面的部分就可以直接施上面的 \(\text{Min-Max}\) 容斥公式了。也就是
\[\begin{aligned} E\left(\max_{i\in S} x_i\right) &= \sum_{y} P(y = x) \max_{j\in S} y_j \\ &= \sum_{y} P(y = x) \sum_{T\subseteq S} (-1)^{\lvert T\rvert - 1} \min_{j\in T} y_j \\ &= \sum_{T\subseteq S} (-1)^{\lvert T\rvert - 1} \sum_{y} P(y = x) \min_{j\in T} y_j \\ &= \sum_{T\subseteq S} (-1)^{\lvert T\rvert - 1} E\left(\min_{i\in S} x_i\right) \end{aligned}\]因此得证。
考虑到上面的容斥，我们不难想到，是否通过一些其他的容斥系数来转化到组合数求和上，从而指向性地得到第 \(k\) 大和第 \(k\) 小。这是可行的，而且我们也可以通过对应公式转化到期望上。这个东西又叫做拓展 \(\text{Min-Max}\) 容斥。
写出：
\[\mathop{\text{k-thmax}}\limits_{i\in S} x_i = \sum_{T\subseteq S} (-1)^{\lvert T\rvert - k} \binom{\lvert T\rvert - 1}{k - 1} \min_{j\in T} x_j \]\[\mathop{\text{k-thmin}}\limits_{i\in S} x_i = \sum_{T\subseteq S} (-1)^{\lvert T\rvert - k} \binom{\lvert T\rvert - 1}{k - 1} \max_{j\in T} x_j \]\[E\left(\mathop{\text{k-thmax}}\limits_{i\in S} x_i \right)= \sum_{T\subseteq S} (-1)^{\lvert T\rvert - k} \binom{\lvert T\rvert - 1}{k - 1} E\left(\min_{j\in T} x_j\right) \]\[E\left(\mathop{\text{k-thmin}}\limits_{i\in S} x_i \right)= \sum_{T\subseteq S} (-1)^{\lvert T\rvert - k} \binom{\lvert T\rvert - 1}{k - 1} E\left(\max_{j\in T} x_j\right) \]不妨设 \(x_i \le x_{i + 1}\)。我们化式子：
\[\begin{aligned} \sum_{T\subseteq S} (-1)^{\lvert T\rvert - k} \binom{\lvert T\rvert - 1}{k - 1} \min_{j\in T} x_j &= \sum_{i\in S} x_i \sum_{T\subseteq S} (-1)^{\lvert T\rvert - k} \binom{\lvert T\rvert - 1}{k - 1} \left[x_i = \min_{j\in T} x_j\right] \\ &= \sum_{i\in S} x_i \sum_{j = k}^n (-1)^{j - k} \binom{j - 1}{k - 1} \binom{n - i}{j - 1} \\ &= \sum_{i\in S} x_i \sum_{j = k}^n (-1)^{j - k} \binom{n - i}{k - 1} \binom{n - i - (k - 1)}{j - 1 - (k - 1)} \\ &= \sum_{i\in S} x_i \sum_{j = k}^n (-1)^{j - k} \binom{n - i}{k - 1} \binom{n - i - k + 1}{j - k} \\ &= \sum_{i\in S} x_i \binom{n - i}{k - 1} \sum_{j = k}^n (-1)^{j - k} \binom{n - i - k + 1}{j - k} \\ &= \sum_{i\in S} x_i \binom{n - i}{k - 1} \sum_{j \ge 0} (-1)^{j} \binom{n - i - k + 1}{j} \\ &= \sum_{i\in S} x_i \binom{n - i}{k - 1} (1 - 1)^{n - k + 1 - i} \end{aligned}\]可以发现 \(C_{n - i}^{k - 1} 0^{n - k + 1 - i} = 1\) 当且仅当 \(i = n - k + 1\)，其余情况都是 \(0\)。这就是第 \(k\) 大值。
其余三个可以类似上面地证明，不再赘述。
因此得证。
可以发现这个东西能够应用到一个数字质因子的指数上，这自然引出了质因子取 \(\min, \max\) 的操作：\(\gcd, \text{lcm}\)。
我们类比地转化操作，有：
这个式子可以叫 \(\gcd\text{-lcm}\) 容斥/反演。
例题：
[HAOI2015] 按位或 - 期望上的 \(\text{Min-Max}\) 容斥;
bzoj4833 最小公倍佩尔数 - \(\gcd\text{-lcm}\) 容斥;
重返现世 - 拓展 \(\text{Min-Max}\) 容斥;
[PKUWC2018] 随机游走 - 对顺序进行期望上的 \(\text{Min-Max}\) 容斥.
一些反演
规定
记一个元素列 \(f\) 的第 \(i\) 个元素为 \(f[i]\)。记一个矩阵 \(A\) 第 \(i\) 行第 \(j\) 列的元素为 \(A[i, j]\)。
一个元素列 \(f\) 对应的向量为 \(\bm f\)。
反演是什么？
我们考虑两个元素列 \(f, g\) 之间的双向关系，这一对关系就叫做反演关系。例如前缀和与差分、倍数求和与倍数差分等。一般地，这类关系是线性的，可以采用一个矩阵 \(A\) 和它的逆来描述，这矩阵又叫做关系矩阵。
一般地，我们可以得到一个关系对应的矩阵 \(A\)，则 \(f\to g\) 的关系可以经由
\[f[k] = \sum_{i \ge 0} A[k, i]\times g[i] \]来描述，也就是 \(\bm f = A\bm g\)。
我们已经可以通过 \(g\) 计算 \(f\) 了，而现在需要用 \(f\) 计算 \(g\)。这样一个过程就叫做反演。不难想到求 \(A\) 的逆矩阵 \(A^{-1}\)，则 \(\bm g = A^{-1}\bm f\)。
例如前缀和矩阵是 \(A[i, j] = [i \ge j]\)，而我们通过求逆能看到 \(A^{-1}[i, j] = [i = j] - [i = j + 1]\)。由定义不难发现两个互为反演关系的关系矩阵互逆。
我们也可以通过这类定义来从原有的反演上得到新的反演。具体地，有以下几条方法：
- 应用转置，容易发现一对互逆矩阵的转置也互逆。
- 可以对两个矩阵分别乘以 \(c \neq 0\)，容易发现这两个矩阵仍然互逆。（这里是一个乘 \(c\) 一个除 \(c\) 的意思吗？）
- 移动 \((-1)^k\) 的指数。我们有\[\sum_{i\ge 0}(-1)^{n - i} A[n, i]\times B[i, m] = [n = m] \quad \Leftrightarrow \quad \sum_{i\ge 0}(-1)^{i} A[n, i]\times (-1)^m B[i, m] = [n = m] \]可以用在一些出现了 \((-1)^{n - k}\) 的时候，比方说二项式反演。
由一维情况可以拓展到二维情况。假设我们有两个关系矩阵 \(A, B\)，他们分别描述了 \(i, j\) 两维的反演信息。我们有这两个关系上矩阵 \(F, G\) 的二维反演：
\[F[n, m] = \sum_{i\ge 0} \sum_{j\ge 0} A[n, i]\times B[m, j]\times G[i, j]\ \Leftrightarrow\ G[n, m] = \sum_{i\ge 0} \sum_{j\ge 0} A^{-1}[n, i]\times B^{-1}[m, j]\times F[i, j] \]发现这就是各维反演系数的乘积。
证明可以构造四维矩阵。
不妨构造 \(C[(i, k), (j, l)] = A[i, j]\times B[k, l]\)，\(D[(i, k), (j, l)] = A^{-1}[i, j]\times B^{-1}[k, l]\)。我们需要证明的就是 \(C\times D = I\)，也就是 \((C\times D)[(i, j), (k, l)] = [(i, j) = (k, l)]\)。
因此得证。
由二维情况可以拓展到多维情况，证明类似，不再赘述。
二项式反演
最基础也最常见的反演。
首先写出第一种形式：
\[f(n) = \sum_{i = 0}^n (-1)^i \binom{n}{i} g(i) \quad \Leftrightarrow\quad g(n) = \sum_{i = 0}^n (-1)^i \binom{n}{i} f(i) \]这依赖着 \(A[n, m] = (-1)^mC_m^n\) 这个矩阵是自逆的。
证明可以写一下 \(A\times A\) 的形式。也就是
\[\begin{aligned} & (A\times A)[n, m] \\ = & \sum_{i \ge 0} A[n, i]\times A[i, m] \\ = & \sum_{i \ge 0} (-1)^i\binom{n}{i} \times (-1)^m\binom{i}{m} \\ = & (-1)^m \sum_{i \ge 0} (-1)^i\binom{n}{i} \binom{i}{m} \\ = & (-1)^m \sum_{i \ge 0} (-1)^i\binom{n}{m} \binom{n - m}{i - m} \\ = & (-1)^m\binom{n}{m} \sum_{i \ge 0} (-1)^i\binom{n - m}{i - m} \\ = & (-1)^m\binom{n}{m} \sum_{i \ge 0} (-1)^{i + m}\binom{n - m}{i} \\ = & \binom{n}{m} \sum_{i \ge 0} (-1)^{i}\binom{n - m}{i} \\ = & \binom{n}{m} 0^{n - m} \\ = & [n = m] \end{aligned}\]我这个证法挺简洁？
然后用上面提过的移动 \((-1)^{n - k}\) 可以得到
\[f(n) = \sum_{i = 0}^n \binom{n}{i} g(i) \quad \Leftrightarrow\quad g(n) = \sum_{i = 0}^n (-1)^{n - i} \binom{n}{i} f(i) \]这个东西也可以 egf 来证。也就是
\[\frac{f(n)}{n!} = \sum_{i = 0}^n \frac{1}{(n - i)!} \frac{g(i)}{i!} \]DNA 动了嘛？构造 \(f, g\) 的 egf \(F, G\)，则 \(F = e^{x}\times G\)，也就能导出 \(G = e^{-x}\times F\)，化一下就能到右边了。
然后用上面提过的转置可以得到
\[f(n) = \sum_{i \ge n} \binom{i}{n} g(i) \quad \Leftrightarrow\quad g(n) = \sum_{i \ge n} (-1)^{i - n} \binom{i}{n} f(i) \]然后用上面提过的移动 \((-1)^{n - k}\) 可以得到
\[f(n) = \sum_{i \ge n} (-1)^i \binom{i}{n} g(i) \quad \Leftrightarrow\quad g(n) = \sum_{i \ge n} (-1)^i \binom{i}{n} f(i) \]这也就是经典的四种式子了。
例题（难度大概逐渐递增？看出题时间和来源也是）：
[NOI Online #2 提高组] 游戏;
已经没有什么好害怕的了
[HAOI2018] 染色;
[TJOI2019] 唱、跳、rap和篮球;
[MtOI2018] 情侣？给我烧了！;
[CTS2019] 随机立方体.
待补。我大概只是为了不让人觉得我一晚上啥都没干吧？
标签：rvert,sum,容斥,times,lvert,反演,原理,binom From： https://www.cnblogs.com/joke3579/p/incl-excl-inversion.html