min-max容斥

描述

Maximum-minimums identity

对于一个集合 $S$ 有

$$
\begin{align}
\max(S) &= \sum_{T \subseteq S} (-1)^{|T|+1} \min(T) \
\min(S) &= \sum_{T \subseteq S} (-1)^{|T|+1} \max(T)
\end{align}
$$

其中 $\max(S)$ 表示集合 $S$ 中的最大元素，$\min(S)$ 表示 $S$ 中的最小元素

证明略

在期望下也成立

$$
\begin{align}
E(\max(S)) &= \sum_{T \subseteq S} (-1)^{|T|+1} E(\min(T)) \
E(\min(S)) &= \sum_{T \subseteq S} (-1)^{|T|+1} E(\max(T))
\end{align}
$$

不会证

例题

随机游走

LOJ #2542. 「PKUWC2018」随机游走

题意

给定一棵 $n$ 个点的树和起点 $x$，每次会等概率地走到相邻的点。

有 $Q$ 次询问，每次给定一个点集 $S$，求经过 $S$ 中每个点至少一次的期望步数。

$x$ 视为一开始就被经过一次。

对 $998244353$ 取模

$n\le 18, Q\le 5000$

做法

记 $t_i$ 表示第一次经过点 $i$ 的时间（不是期望）

假设询问的集合是 ${a_1,a_2,\dotsc,a_k}$

令 $S={t_{a_1},t_{a_2},\dotsc,t_{a_k}}$

答案即为 $E(\max(S))$

根据上面的等式，问题转化为求

$$
\sum_{T \subseteq S} (-1)^{|T|+1} E(\min(T))
$$

假如求出了每个 $E(\min(T))$，直接枚举复杂度是 $\mathcal O(3^n)$，高维前缀和 $\mathcal O(n\times 2^n)$

考虑如何求一个 $E(\min(T))$，这等于走到 $T$ 中任意一个点即停止的期望步数

令 $f_u$ 表示从 $u$ 出发的期望步数，因此 $E(\min(T))=f_x$

以 $x$ 为根，记 $u$ 的度数为 $d_u$，$u$ 的父亲为 $fa_u$

对于 $u\in T$ 有 $f_u=0$

对于一般的节点 $u$，有

$$
f_u=\frac{f_{fa_u}+\sum_{v \text{是} u \text{的儿子}} f_v}{d_u}+1
$$

显然任意一个 $u\in T$ 的子树都不需要考虑

直接高斯消元是 $\mathcal O(n^3)$ 的

对于树上的问题有更好的做法

设 $f_u=a_u f_{fa_u}+b_u$

显然对于 $u\in T$ 有 $a_u=b_u=0$

假设我们已经求出 $u$ 每个儿子 $v$ 的 $a_v, b_v$

代入有

$$
d_u f_u=f_{fa_u}+ \left(\sum_{v \text{是} u \text{的儿子}} a_v f_u \right)+ \left(\sum_{v \text{是} u \text{的儿子}} b_v \right) +d_u
$$

整理得到

$$
f_u=\frac{f_{fa_u} + \left( \sum_{v \text{是} u \text{的儿子}} b_v \right) + d_u}{d_u-\sum_{v \text{是} u \text{的儿子}} a_v}
$$

因此

$$
a_u = \frac{1}{d_u-\sum_{v \text{是} u \text{的儿子}} a_v} ,
b_u = \frac{d_u+ \sum_{v \text{是} u \text{的儿子}} b_v}{d_u-\sum_{v \text{是} u \text{的儿子}} a_v}
$$

根节点 $x$ 没有父亲，即 $f_x=b_x$

单次时间 $\mathcal O(n \times \log 998244353)$

总复杂度 $\mathcal O(n \times \log 998244353 \times 2^n)$

代码

#include<cstdio>
#include<algorithm>
#include<cctype>
#include<string.h>
#include<cmath>

using namespace std;
#define ll long long

const int N = 20, P = 998244353, M = 1<<18;
int n, q, r, num, d[N], a[N], b[N], h[N], e[N<<1], pre[N<<1];
ll f[M];
bool ban[N];
inline void add(int x, int y){ e[++num]=y, pre[num]=h[x], h[x]=num;}
inline int Pow(ll x, int y=P-2){
	int ans=1;
	for(; y; y>>=1, x=x*x%P) if(y&1) ans=ans*x%P;
	return ans;
}
void dfs(int u, int fa=0){
	if(ban[u]) return (void)(a[u]=b[u]=0);
	ll sa=0, sb=0;
	for(int i=h[u]; i; i=pre[i]) if(e[i]!=fa)
		dfs(e[i], u), sa+=a[e[i]], sb+=b[e[i]];
	a[u]=Pow((d[u]-sa)%P+P), b[u]=(sb+d[u])%P*a[u]%P;
}
int main() {
	scanf("%d%d%d", &n, &q, &r);
	for(int i=1, x, y; i<n; ++i)
		scanf("%d%d", &x, &y), add(x, y), add(y, x), ++d[x], ++d[y];
	for(int i=0; i<1<<n; ++i){
		bool cnt=0;
		for(int j=0; j<n; ++j) cnt^=ban[j+1]=i>>j&1;
		dfs(r), f[i]=(cnt?b[r]:P-b[r]);
	}
	for(int i=1; i<1<<n; i<<=1) for(int j=0; j<1<<n; j+=i<<1) for(int k=j; k<j+i; ++k)
		f[k+i]+=f[k];
	while(q--){
		int k, s=0, x;
		scanf("%d", &k);
		while(k--) scanf("%d", &x), s|=1<<(x-1);
		printf("%d\n", (int)(f[s]%P));
	}
	return 0;
}

按位或

LOJ #2127. 「HAOI2015」按位或

题意

你有一个数字 $0$，每秒你会以 $p_i$ 的概率选择 $i$，$i\in[0,2^n-1]$，和自己的数进行按位或，问期望多少秒后数字变成 $2^n-1$

$n\le20,\sum p_i=1$

做法

不用 min-max容斥的做法在 这里.

网上很多我就不写了