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容斥的做法在 这里.

网上很多我就不写了