二项式反演和 Min-Max 反演小记-526互联

二项式反演

本质上是某种容斥。

结论为：

\[f_i = \sum_{j=0}^i(-1)^j\binom{i}{j}g_j\Leftrightarrow g_i = \sum_{j=0}^i(-1)^j\binom{i}{j}f_j \]

更常用的形式是

\[f_i = \sum_{j=0}^i \binom{i}{j}g_j\Leftrightarrow g_i = \sum_{j=0}^i(-1)^{i-j}\binom{i}{j}f_j \]

证明第二个式子（EGF 证法）：

记 \(f\) 的指数生成函数为 \(F(x)\)，\(g\) 的指数生成函数为 \(G(x)\)。
那么

\[\begin{split} &F(x) = \mathrm{e}^{x}G(x)\\ &G(x) = \mathrm{e}^{-x}F(x)\\ &g_i =i!\sum_{j=0}^i\frac{(-1)^{i-j}}{(i-j)!}\frac1{j!}f_j=\sum_{j=0}^i(-1)^{i-j}\binom{i}{j}f_j\\ &\Box \end{split} \]

实际上还有一种形式：

\[f_i = \sum_{j=i}(-1)^j\binom{j}{i}g_j\Leftrightarrow g_i = \sum_{j=i}(-1)^j\binom{j}{i}f_j \]

或者写成：

\[f_i = \sum_{j=i}\binom{j}{i}g_j\Leftrightarrow g_i = \sum_{j=i}(-1)^{i-j}\binom{j}{i}f_j \]

错排问题

长度为 \(n\) 的排列 \(p\) 若对于 \(1\le i\le n\) 满足 \(i\not= p_i\)，称它为一个错位排列。

将长度为 \(n\) 的错位排列数记为 \(D_n\)。

需要快速地求出某一 \(D_n\)。

对于所有长度为 \(n\) 的排列 \(p\)，有 \(k\) 个 \(i\) 满足 \(p_i\not= i\) 的排列 \(p\) 的个数为 \(\binom{n}{k}D_k\)。

考虑枚举 \(k\) 即有：

\[n! = \sum_{i=0}^n\binom{n}{k}D_k \]

套用反演结论即有

\[D_n = \sum_{i=0}^n(-1)^{n-i}\binom{n}{k}k!=n!\sum_{i=0}^n(-1)^{i}\frac1{i!} \]

QOJ#5826 GDKOI2023TG D1T2

求有几个长度为 \(n\) 的排列 \(p\) 满足 \(\forall 1\le i\le m, p_i>m\) 且 \(\forall 1\le i\le n, p_i\not=i\)， \(\operatorname{mod} 998244353\)。

不会正解，推个基本的式子。

考虑先在 \([m+1, n]\) 点 \(m\) 个数填在前 \(m\) 个位置上，然后将剩下除 \([1, m]\) 的 \(n-2m\) 个数填掉，最后把 \([1, m]\) 直接填进去。

发现第一步会有一个 \(\frac{(n-m)!}{(n-2m)!}\) 的系数，第三步会有一个 \(m!\) 的系数，把这两步系数的乘积记为 \(k\)，而第二步的系数不太好计算，类似于原版错排问题。

枚举第二步中 \(p_i=i\) 的位置的个数：

\[k\binom{n-m}{n-2m}=\sum_{i=0}^{n-2m}\binom{n-2m}{i}f_i \]

令 \(l = n-2m\)，那么

\[k\binom{l+m}{l}=\sum_{i=0}^{l}\binom{l}{i}f_i \]

反演得

\[f_l = k\sum_{i=0}^l(-1)^{l - i}\binom{l}{i}\binom{i+m}{i} \]

BZOJ3622 已经没什么好害怕的了

给定两个长度为 \(n\) 的序列 \(a,b\)，将 \(a\) 与 \(b\) 两两配对，求 \(a\) 比 \(b\) 大的组恰好有 \(k\) 个的方案数。

\(n\le 2000\)

容斥dp

恰有 \(k\) 组不太好求，考虑用容斥变为钦定 \(k\) 组，其余随意。

用 \(g_i\) 表示恰有 \(i\) 组的方案数，\(f_i\) 表示钦定 \(i\) 组的方案数，那么：

\[f_k(n-k)! = \sum_{i=k}^n\binom{i}{k}g_i \]

这个式子珂能不太好理解，左边的意思是钦定 \(k\) 对，其余任选；右边的意思是对于每个 \(i\ge k\) 都可以点 \(k\) 组来钦定，因此这个式子是正确的。

这个式子可以直接套另一种二项式反演。

\[f_k(n-k)! = \sum_{i=k}^n\binom{i}{k}g_i \]

考虑将 \(f\) 数组 dp 出来：

\(f_{i,j}\) 表示当前 dp 到 \(i\)，已经钦定了 \(j\) 对的方案数。

我们将 \(a, b\) 分别降序排序，方便 dp。

用 \(mx_i\) 表示 \(a_i\) 可以匹配的数的个数，那么可以轻易写出状态转移方程：

\[f_{i, j}=f_{i-1, j} + (mx_i-j+1)f_{i-1, j-1} \]

时间复杂度 \(\mathcal{O(n^2)}\)。

Min-Max 反演

首先由二项式定理可以得到一个式子

\[\sum_{T\subseteq S}(-1)^{|T|} = [S=\varnothing] \]

这个式子是好证明的：

\[\sum_{T\subseteq S}(-1)^{|T|} = \sum_{i=0}^{|S|}\binom{|S|}{i}(-1)^i = (1-1)^{|S|} = [S = \varnothing] \]

Min-Max 反演的结论式为：

\[\max S = \sum_{T\subseteq S \land T \not= \varnothing} (-1)^{|T| - 1}\min T\\ \min S = \sum_{T\subseteq S \land T \not= \varnothing} (-1)^{|T| - 1}\max T \]

证明第一个式子，第二个式子的证明是类似的

\[\begin{split} &\max S \\ =&\sum_{x\in S}x[\{y|y>x\} = \varnothing]\\ =&\sum_{x\in S}x\sum_{T\subseteq\{y|y>x\}}(-1)^{|T|}\\ =&\sum_{T\in S \land T \not= \varnothing} (-1)^{|T| - 1}\min T \end{split} \]

期望形式同样成立：

\[E(\max S) = \sum_{T\subseteq S \land T \not= \varnothing} (-1)^{|T| - 1}E(\min T)\\ E(\min S) = \sum_{T\subseteq S \land T \not= \varnothing} (-1)^{|T| - 1}E(\max T) \]

Luogu P3175 [HAOI2015] 按位或

考虑对于每一位分别考虑，答案就是每一位第一次出现的时间的最大值。

最大值是不好处理的，使用 Min-Max 反演转化成最小值。

\(\min S = \dfrac1{\sum_{T\cap S\not ={\varnothing}}p_{T}}\)

发现交不为空实际上就是状压后位与起来不等于 \(0\)，这个不好求，考虑求出位与起来等于 \(0\) 的和减一下就好了，位与起来为 \(0\) 也就是将 \(S\) 取反后 \(T\) 为 \(S\) 的子集，直接高维前缀和即可。

还有一道很神的题，这里是题解： Luogu P5643 [PKUWC2018]随机游走

Min-Max 反演推广——Kth Min-Max 反演

如何将一个集合中的第 \(k\) 大转化成子集 \(\min\) 呢？

发现 Min-Max 中用的结论是

\[\sum_{T\subseteq S}(-1)^{|T|} = [S=\varnothing] \]

如果找到函数 \(f(x)\) 使得 \( \sum_{T\subseteq S}f(|T|) = [|S|=k-1]\)，就可以得出 Kth Min-Max 反演的式子。

我推的柿子：

\[\begin{split} &\sum_{T\subseteq S}f(|T|) = [|S|=k-1]\\ &\sum_{i=0}^{|S|}\binom{|S|}{i}f(i) = [|S|=k-1] \end{split} \]

二项式反演得

\[f(x) = \sum_{i=0}^x(-1)^{x-i}\binom{x}{i}[i=k-1]=(-1)^{x-k+1}\binom{x}{k-1} \]

于是可以写出 Kth Min-Max 反演的式子：

\[\operatorname{kth-max}S=\sum_{T\subseteq S\land T\not ={\varnothing}}(-1)^{|T|-k}\binom{|T|-1}{k-1}\min T\\ \operatorname{kth-min}S=\sum_{T\subseteq S\land T\not ={\varnothing}}(-1)^{|T|-k}\binom{|T|-1}{k-1}\max T \]

期望形式同样成立。

Luogu P4707 重返现世

首先用 Kth Min-Max 反演：

\[E(\operatorname{kth-max}S) = \sum_{T\subseteq S\land T\not ={\varnothing}}(-1)^{|T|-k}\binom{|T|-1}{k-1}E(\min T)\\ \]

注意到此处的 \(k\) 和题面中意义不同，实际上是 \(n-k+1\)，所以非常小。

若用 \(\operatorname{sum}{S}\) 表示集合 \(S\) 中所有元素的和，则 \(E(\min T) = \dfrac m{\operatorname{sum}T}\)，此处两个 \(T\) 第一个是表示第一次出现的时间集合，第二个是表示出现概率 \(p_i\) 的集合。

于是柿子变为：

\[E(\operatorname{kth-max}S) = (-1)^k\sum_{T\subseteq S\land T\not ={\varnothing}}(-1)^{|T|}\binom{|T|-1}{k-1}\dfrac m{\operatorname{sum}T}\\ \]

考虑 dp 求出这个和式。

可以对于所有的 \(|T|\) 和 \(\operatorname{sum}T\) 求出其方案数，这样就可以计算了。这个是好容易用 dp 解决的，一个一个数考虑加不加入即可，但这样的时间复杂度是 \(\mathcal{O}(n^2m)\) 的，且没有用到 \(k\) 特别小的条件。

考虑减少状态，发现 \(\operatorname{sum}T\) 不好消去，只能把 \(|T|\) 这一维消去。

那么需要对于每个 \(j = \operatorname{sum}T\) 求出

\[\sum_{\operatorname{sum}T=j} (-1)^{|T|}\binom{|T|-1}{k-1} \]

考虑加入一个数时（也就是 \(|T|\) 增加 \(1\) 时）这个柿子会发生什么变化，可以发现 \((-1)^{|T|}\) 会取反且 \(\binom{|T|-1}{k-1}\) 会变成 \(\binom{|T|}{k-1}\)，这个二项式系数发生了什么变化呢，观察不到 \(\binom{|T|}{k-1} = \binom{|T|-1}{k-1} + \binom{|T|-1}{k-2}\)，于是可以在 dp 中记录 \(k\) 这一维进行递推。

\(f_{i, j, d}\) 表示当前 dp 到 \(i\) 时的 \(\sum\limits_{\operatorname{sum}T=j} (-1)^{|T|}\binom{|T|-1}{d}\)，那么可以写出状态转移方程：

\[\begin{split} f_{i, j, d} &\gets f_{i-1, j, d}\\ f_{i, j, d} &\gets -(f_{i-1, j-p_i, d} + f_{i-1, j-p_i, d-1}) \end{split} \]

这样做时间复杂度是 \(\mathcal{O}(nmk)\)，空间上可以将第一维滚掉。

\[\mathcal{-END-} \]