0%

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)\)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#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容斥的做法在 这里.

网上很多我就不写了