容斥 & 反演

· · 算法·理论

集合反演

f(S)=\sum\limits_{T\subseteq S}g(T) g(S)=\sum\limits_{T\subseteq S} (-1)^{|S|-|T|}f(T)

或者

f(S)=\sum\limits_{S\subseteq T}g(T) g(S)=\sum\limits_{S\subseteq T} (-1)^{|T|-|S|}f(T)

CF1770F Koxia and Sequence

给定非负整数 n,x,y，对于所有满足 \sum\limits_{i=1}^{n}a_i=x 并且 \text{OR}_{i=1}^{n}a_i=y 的 \{a_n\}，求 \bigoplus\limits_{i=1}^{n}a_i 的异或和。

- 题解 首先根据对称性，当 $n$ 为偶数时，答案为 $0$。所以只考虑 $n$ 为奇数的情况，为 $a_1$ 的异或和。 拆位，对每一位 $t$，计算 $a_1$ 的第 $t$ 位为 $1$ 的方案数 $\text{mod}\ 2$ 的结果。此时显然 $\bigoplus\limits_{i=1}^{n}a_i$ 第 $t$ 位为 $1$。 考虑容斥，设 $g(y)$ 为按位或为 $y$ 的方案数，$f(y)$ 为按位或为 $y$ 的子集的方案数，显然 $f(y)=\sum\limits_{y'\subseteq y}g(y')$，反演结论得到 $g(y)=\sum\limits_{y'\subseteq y}(-1)^{|y|-|y'|}f(y')$，前提是 $y'$ 第 $t$ 位为 $1$。 由于我们只需要得到 $g(y)$ 的奇偶性，所以我们可以将式子变为 $g(y)\equiv\bigoplus\limits_{y'\subseteq y}f(y')\mod 2$。 因为钦定 $a_1$ 的第 $t$ 位为 $1$，我们可以让 $a_1$ 减去 $2^t$，此时 $\sum\limits_{i=1}^{n}a_i=x-2^t$。 由 $\text{Lucas}$ 定理推论（组合数奇偶性定理）与 $\text{Vandermonde}$ 卷积公式得： $$\begin{aligned}f(y)&=\sum\limits_{\sum\limits a_i=x-2^t}[a_1\subseteq y-2^t][a_2\subseteq y][a_3\subseteq y]...[a_n\subseteq y]\\&\equiv\sum\limits_{\sum a_i=x-2^t}\dbinom{y-2^t}{a_1}\dbinom{y}{a_2}\dbinom{y}{a_3}...\dbinom{y}{a_n}\mod 2\\&\equiv\dbinom{ny-2^t}{x-2^t}\mod 2\\&\equiv [x-2^t\subseteq ny-2^t]\mod 2\end{aligned}$$ 所以答案即为： $$\begin{aligned}\sum\limits_{t}2^tf(y)&=\sum\limits_t 2^t\bigoplus\limits_{y'\subseteq y,2^t\in y'}g(y')\\&=\sum\limits_t 2^t\bigoplus\limits_{y'\subseteq y,2^t\in y'}[x-2^t\subseteq ny-2^t]\end{aligned}$$ $O(y\log y)$ 枚举 $t,y'$ 即可。 #### SHOI2016 黑暗前的幻想乡 - 题意： $n$ 个点，$n-1$ 种颜色。每种颜色有 $m_i$ 条边连接 $u_j,v_j$ 两个节点。求颜色数为 $n-1$ 的生成树数量。 $n\le 17$。 - 题解： 实在不会一些不太板的数数题…… 考虑以颜色为集合状态，令 $f_{S}$ 为恰有 $S$ 中颜色的生成树数量，$g_{S}$ 为颜色在 $S$ 中的生成树数量。 显然有 $g_{S}=\sum\limits_{T\subseteq S}f_T$。那么 $f_S=\sum\limits_{T\subseteq S}(-1)^{|S|-|T|}g_T$。 所以答案就是 $f_U=\sum\limits_{T}(-1)^{n-1-|T|}g_T$，枚举 $T$ 然后把 $T$ 所有颜色拉出来求无向图生成树个数即可。 可以 $\text{matrix\ tree}$ 定理。复杂度 $O(2^nn^3)$。 #### 二项式反演 这个形式有点多，最常用的： $$f(n)=\sum\limits_{i=0}^n\dbinom{n}{i}g(i)$$ $$g(n)=\sum\limits_{i=0}^n(-1)^{n-i}\dbinom{n}{i}f(i)$$ 不太常用的： $$f(n)=\sum\limits_{i=0}^n(-1)^i\dbinom{n}{i}g(i)$$ $$g(n)=\sum\limits_{i=0}^n(-1)^{i}\dbinom{n}{i}f(i)$$ 这主要告诉我们 $A_{ii}=(-1)^i\dbinom{n}{i}$ 这个矩阵是**自逆**的。 例题有点板。我数学怎么这么菜。 #### 莫比乌斯反演 形式 $1$（约数形式）： $$f(n)=\sum\limits_{d\mid n} g(d)$$ $$g(n)=\sum\limits_{d\mid n}\mu(d)f(\frac{n}{d})$$ 这是显然的，由 $f=g*I,\mu =I^{-1}$ 可推出 $g=f*\mu$。 形式 $2$（倍数形式）： $$f(n)=\sum\limits_{n\mid d}g(d)$$ $$g(n)=\sum\limits_{n\mid d}\mu(\frac{d}{n})f(d)$$ 这鬼东西有点抽象，找时间补个证明。 一般用于解决数论问题，找不到什么高妙不板的例题。 --- 下面是科技。 #### Min-Max 容斥 对于满足全序关系并且其中元素满足可加减性的**可重**集合 $S$，有： $$\max\{S\}=\sum\limits_{T\subseteq S}(-1)^{|T|-1}\min\{T\}$$ $$\min\{S\}=\sum\limits_{T\subseteq S}(-1)^{|T|-1}\max\{T\}$$ 证明（参考 `OI Wiki` ）： 考虑构造映射 $f:S_k\to \{1,2,...,k\}$，$S_k$ 为 $S$ 中第 $k$ 大元素，显然这是双射。 那么 $f(\min(x,y))=f(x)\cap f(y),f(\max(x,y))=f(x)\cup f(y)$。 所以： $$\begin{aligned}\begin{vmatrix}f(\max\{S\})\end{vmatrix}&=\begin{vmatrix}\bigcup\limits_{t\in S}f(t)\end{vmatrix}\\&=\sum\limits_{T\subseteq S}(-1)^{|T| -1}\begin{vmatrix}\bigcap\limits_{t\in T}f(t)\end{vmatrix}\\&=\sum\limits_{T\subseteq S}(-1)^{|T| -1}\begin{vmatrix}f(\min\{T\})\end{vmatrix}\end{aligned}$$ 两边的 $f$ 都可以映射回去，用类似的证法可以把左式换成最小值，所以 $\text{Min-Max}$ 容斥成立。 事实上，$\text{Min-Max}$ 容斥也可以作用于期望： $$E(\max\{S\})=\sum\limits_{T\subseteq S}(-1)^{|T|-1}E(\min\{T\})$$ $$E(\min\{S\})=\sum\limits_{T\subseteq S}(-1)^{|T|-1}E(\max\{T\})$$ 证明可以考虑期望的定义式，注意 $S_0$ 代表 $S$ **所有可能出现元素**的并： $$\begin{aligned}E(\max\{S\})&=\sum\limits_{S'\subseteq S_0}P(S'=S)\max\{S'\}\\&=\sum\limits_{S'\subseteq S_0}P(S'=S)\sum\limits_{T\subseteq S'}(-1)^{|T|-1}\min\{T\}\\&=\sum\limits_{T\subseteq S_0}(-1)^{|T|-1}\sum\limits_{T\subseteq S'}P(S'=S)\min\{T\}\\&=\sum\limits_{T\subseteq S_0}(-1)^{|T|-1}E(\min(T))\end{aligned}$$ 需要注意的是倒数第二行 $\sum\limits_{T\subseteq S'}P(S'=S)\min\{T\}$ 中即使 $S'$ 带附加条件，这个式子仍然表示的是 $T$ 的期望最小值，理由可以自行思考（ #### HAOI2015 按位或 - 题意： 刚开始你有一个数字 $0$，每一秒钟你会随机选择一个 $[0,2^n-1]$ 的数字，与你手上的数字进行或（C++,C 的 `|`，pascal 的 `or`）操作。选择数字 $i$ 的概率是 $p_i$。保证 $0\leq p_i \leq 1$，$\sum p_i=1$ 。问期望多少秒后，你手上的数字变成 $2^n-1$。 $n\le 20$。 - 题解： 根据 $\text{Min-Max}$ 容斥原理： $$E(\max\{S\})=\sum\limits_{T\subseteq S} (-1)^{|T|-1}E(\min\{T\})$$ 本题中 $S$ 代表一个位数的集合，$\max\{S\}$ 为 $S$ 中元素最后一个变为 $1$ 的时间，$\min\{T\}$ 为 $T$ 中元素第一个变为 $1$ 的时间，显然答案就是左式 $E(max\{S\})$。 考虑求解 $E(\min\{T\})$，由于 $T$ 中至少有一个元素变为 $1$ 的概率为 $\sum\limits_{T'\cap T\neq \varnothing}P_{T'}$，根据期望的定义我们知道 $E(\min\{T\})=\dfrac{1}{\sum\limits_{T'\cap T\neq \varnothing}P_{T'}}$，其中 $U$ 表示全集 $\{0,1,...,n-1\}$。 这个有交的东西比较难搞，正难则反，考虑 $U$ 的补集，则 $E(\min\{T\})=\dfrac{1}{\sum\limits_{T'\cap T\neq \varnothing}P_{T'}}=\dfrac{1}{1-\sum\limits_{T'\subseteq U\setminus T}P_{T'}}$。 于是问题变为求解 $\sum\limits_{T'\subseteq T}P_{T'}$，这显然是一个 `FWT` 的或运算变换，直接 $O(n2^n)$ 做即可。 最后枚举每个 $T$，求其贡献即可，复杂度 $O(n2^n)$。 #### PKUWC2018 随机游走 - 题意： 给定一棵 $n$ 个结点的树，你从点 $x$ 出发，每次等概率随机选择一条与所在点相邻的边走过去。 有 $Q$ 次询问，每次询问给定一个集合 $S$，求如果从 $x$ 出发一直随机游走，直到点集 $S$ 中所有点都至少经过一次的话，期望游走几步。 特别地，点 $x$（即起点）视为一开始就被经过了一次。 $n\le 18$，$Q\le 5000$，对 $998244353 $ 取模。 - 题解： 求集合内最大时间的期望，一眼 $\text{Min-Max}$ 容斥。 $$E(\max\{S\})=\sum\limits_{T\subseteq S} (-1)^{|T|-1}E(\min\{T\})$$ ~~为什么我每题都要写一遍这个式子。~~ 左式即为所求，考虑右式 $E(\min\{T\})$ 怎么做，它的意义为对于每一个 $T\subseteq S$，求出随机游走并第一次走到 $u\in T$ 的期望时间。 对于随机游走问题，可以用 dp 解决。 设 $f_{T,i}$ 表示树上从 $i$ 游走到第一个 $T$ 中的点的期望时间。 那么显然： - $f_{T,i}=0,i\in T

应该注意的是这里状态转移之间包含了环，所以不能直接从下往上或从上往下递推。

对于这类随机游走问题，我们一般使用高斯消元求解，但是这题使用高斯消元是 O(n^3) 的，预处理就需要 O(2^nn^3\log w)，显然超时。但是树上随机游走问题我们有一些特殊的技巧。

为了简化算式，以下 f_{T,i} 简记为 f_i，读者需要知道这是对于每一个 T 而言的。

首先考虑叶子节点 u，显然它能够被表示成 A_u+B_u\times f_{fa_u} 的形式：如果 u\in T，那么 A_u=B_u=0，否则 A_u=B_u=1。

然后我们考虑归纳，假设节点 u 的所有儿子 v_1,v_2,...,v_m 均可以表示成 A_{v_i}+B_{v_i}\times f_u 的形式，那么对于节点 u ：

\begin{aligned}f_u=1+\frac{1}{deg_u}\left(f_{fa_u}+\sum\limits_{i=1}^mA_{v_i}+B_{v_i}\times f_u\right)\end{aligned}

那就解一个方程即可：

f_u=\dfrac{deg_u+\sum\limits_{i=1}^{m}A_{v_i}}{deg_u-\sum\limits_{i=1}^{m}B_{v_i}}+\dfrac{f_{fa_u}}{deg_u-\sum\limits_{i=1}^{m}B_{v_i}}

令 A_u=\dfrac{deg_u+\sum\limits_{i=1}^{m}A_{v_i}}{deg_u-\sum\limits_{i=1}^{m}B_{v_i}}，B_u=\dfrac{1}{deg_u-\sum\limits_{i=1}^{m}B_{v_i}} 即可满足 f_u=A_u+B_{u}\times f_{fa_u}。

那么我们令 x 作为根，从儿子向根递推能得到每个点的 A_u,B_u，由于 x 没有父亲，那么 f_{T,x}=A_x，我们就能 O(2^nn\log w) 得到对于每一个 T，E(\min\{T\}) 的值，记为 g_{T}。

那么对于每一个 S，我们只需要求 \sum\limits_{T\subseteq S}(-1)^{|T|-1}g_{T}，跑 FWT 或变换即可。

拓展 Min-Max 容斥

由于我被神仙 sinsop90 踩爆了，所以添加一点内容。

事实上，\text{Min-Max} 容斥可以求出第 k 大小：

\max_k\{S\}=\sum\limits_{T\subseteq S}(-1)^{|T|-k}\dbinom{|T|-1}{k-1}\min\{T\} \min_k\{S\}=\sum\limits_{T\subseteq S}(-1)^{|T|-k}\dbinom{|T|-1}{k-1}\max\{T\} E(\max_k\{S\})=\sum\limits_{T\subseteq S}(-1)^{|T|-k}\dbinom{|T|-1}{k-1}E(\min\{T\}) E(\min_k\{S\})=\sum\limits_{T\subseteq S}(-1)^{|T|-k}\dbinom{|T|-1}{k-1}E(\max\{T\})

证明略。

P4707 重返现世

有 n 种原料，需要集齐任意 k 种。

每个单位时间会随机生成一种原料。每种原料被生成的概率是不同的，第 i 种原料被生成的概率是 \frac{p_i}{m} 。

求收集到任意 k 种原料的期望时间，答案对 998244353 取模。

- 题解： 我们可以把题目看作每个原料有一个生成时间，即求第 $n-k+1$ 大的期望值。为了简化式子，以下令 $k\gets n-k+1$，显然 $k\le 11$，并且求的是第 $k$ 大的期望。 套用拓展 $\text{Min-Max}$ 容斥，把前 $k$ 大转换成最小： $$E(\max\limits_{k}(S))=\sum\limits_{T\subseteq S} \dbinom{|T|-1}{k-1}(-1)^{|T|-k}E(\min(T))$$ 显然对于每一种 $T$，可以把 $T$ 中的原料看成一类，其它的看作另一类，那么抽到 $T$ 中原料的概率显然就是 $P_T=\dfrac{\sum\limits_{i\in T}p_i}{m}$，由于$E(\min(T))$ 表示第一次抽到 $T$ 中原料的期望时间，所以由简单期望知识我们知道 $E(\min(T))=\dfrac{1}{P_T}=\dfrac{m}{\sum\limits_{i\in T}p_i}$。 所以 $$\begin{aligned}ans_k&=\sum\limits_{T\subseteq S} \dbinom{|T|-1}{k-1}(-1)^{|T|-k}\dfrac{m}{\sum\limits_{i\in T}p_i}\\&=m\sum\limits_{T\subseteq S} \dfrac{\dbinom{|T|-1}{k-1}(-1)^{|T|-k}}{\sum\limits_{i\in T}p_i}\end{aligned}$$ 然后考虑 $dp$，由于 $k$、$m$ 都很小，于是可以纳入状态，令 $dp_{i,j,k}$ 表示当前考虑前 $i$ 种原料，$\sum\limits_{i\in T}p_i=j$ 的时候 $\sum\limits_{T\subseteq S}\dbinom{|T|-1}{k-1}(-1)^{|T|-k}$ 的值。 转移的话，其实非常显然。 - 首先你可以不取 $i$，$dp_{i,j,k}\gets dp_{i-1,j,k}$。 - 其次，如果你选了 $i$，那么： $\dbinom{|T|-1}{k-1}(-1)^{|T|-k}=\dbinom{|T|-2}{k-2}(-1)^{(|T|-2)-(k-2)}-\dbinom{|T|-2}{k-1}(-1)^{(|T|-2)-(k-1)}

于是这种情况可以从 dp_{i-1,j-p_i,k} 与 dp_{i-1,j-p_i,k-1} 转移过来。

总的转移式子就是：

dp_{i,j,k}=dp_{i-1,j,k}+dp_{i-1,j-p_i,k-1}-dp_{i-1,j-p_i,k} #### 单位根反演 $$[n\mid k]=\frac{1}{n}\sum\limits_{d=0}^{n-1}\omega_{n}^{ik}$$ 这个东西没啥用，但是： **单位根反演常用于求某个多项式特定倍数的系数和。** $$\begin{aligned}\sum\limits_{i=0}^{\lfloor\frac{n}{k}\rfloor}[x^{ik}]f(x)&=\sum\limits_{i=0}^n[k\mid i][x^i]f(x)\\&=\sum\limits_{i=0}^n[x^i]f(x)\frac{1}{k}\sum\limits_{j=0}^{k-1}\omega_{k}^{ij}\\&=\frac{1}{k}\sum\limits_{i=0}^na_i\sum\limits_{j=0}^{k-1}\omega_{k}^{ij}\\&=\frac{1}{k}\sum\limits_{i=0}^n\sum\limits_{j=0}^{k-1}a_i(\omega_k^j)^i\\&=\frac{1}{k}\sum\limits_{j=0}^{k-1}f(\omega_k^j)\end{aligned}$$ 推论： $$\sum\limits_{i=0}^{\lfloor\frac{n}{k}\rfloor}[x^{ik+r}]f(x)=\frac{1}{k}\sum\limits_{j=0}^{k-1}f(\omega_k^j)\omega_{k}^{-ir}$$