min-max容斥学习笔记

众所周知，min-max 容斥简称容斥原理，或称简单容斥，或称二项式反演，是一类可以在 $O(2^n)$ 的时间内求出大小为 $n$ 的集合的元素最小值的优秀算法……

公式

min-max 容斥即是这个柿子：

$$\begin{align} k\text{-th}\min S&= \sum\limits_{T\subseteq S, T\neq \emptyset} (-1)^{|T|-k}\dbinom{|T|-1}{k-1} \max T \tag 1\newline k\text{-th}\max S&= \sum\limits_{T\subseteq S, T\neq \emptyset} (-1)^{|T|-k}\dbinom{|T|-1}{k-1} \min T \tag 2\end{align}$$

证明如下。

假设存在一个系数函数 $f(x)$，使得：

$$k\text{-th}\min S= \sum\limits_{T\subseteq S, T\neq \emptyset} f(|T|) \max T$$

那么集合中第 $x$ 小值在求和中的系数是 $\sum\limits_{i=0}^{x-1} \dbinom{x-1}{i}f(i+1)$，比较系数得：

$$ [n+1=k] = \sum\limits_{i=0}^n\dbinom{n}{i}f(i+1)$$

二项式反演得：

$$\begin{aligned} f(n+1)&=\sum\limits_{i=0}^n(-1)^{n-i}\dbinom{n}{i}[i+1=k]\newline &= (-1)^{n+1-k}\dbinom{n}{k-1}\end{aligned} $$

从而有 $f(x)=(-1)^{x-k}\dbinom{x-1}{k-1}$，它对任意合法的 $k$ 取值均有定义，于是 $(1)$ 式得证。

$(2)$ 式也可以通过类似的方法证明，此处省略。

在 $(1),(2)$ 中取 $k=1$，还可以得到：

$$\begin{align}\min S&=\sum\limits_{T\subseteq S,T\neq \emptyset} (-1)^{|T|-1} \tag 3\max T\newline \max S&=\sum\limits_{T\subseteq S, T\neq \emptyset} (-1)^{|T|-1}\min T \tag 4\end{align}$$

一道栗题

设数列 $f[0]=0,f[1]=1,f[i]=f[i-1]+f[i-2](i>1)$ 是斐波那契数列。给定由若干正整数构成的集合 $S$，试求 $\text{lcm}_{x\in S} f[x]$，对 $10^9+7$ 取模。
$|S|\le 50000, x\le 10^6$

考虑 $\text{lcm } a,b=\prod\limits_i p_i^{\max e_i,e’_i}$，其中 $p_i$ 是素数，$e_i$ 和 $e’_i$ 分别是 $a,b$ 标准分解的指数。根据 $(f[a],f[b])=f[(a,b)]$，对指数 min-max 容斥得到：

$$\begin{align} \text{lcm}_{i\in S} f[i]&=\prod\limits_{T\subseteq S,T\neq \emptyset} \text{gcd}_{i\in T}f[i]^{(-1)^{|T|-1}} \newline &=\prod\limits_{T\subseteq S,T\neq \emptyset} f[\text{gcd}_{i\in T}i]^{(-1)^{|T|-1}}\end{align}$$

设 $f[n]=\prod\limits_{d|n} g[d]$，简记 $\text{gcd}_{i\in T}i=\text{gcd}T$，那么有：

$$\begin{align} \text{lcm}_{i\in S} f[i]&=\prod\limits_{T\subseteq S,T\neq \emptyset}\prod\limits_{d|\text{gcd}T}g[d]^{(-1)^{|T|-1}}\newline &=\prod\limits_dg[d]^{\sum_{T\subseteq S,T\neq\emptyset}[d|\text{gcd}T](-1)^{|T|-1}} \end{align}$$

设 $t=\sum\limits_{x\in S}[d|x]$，考虑指数那一部分，当 $t=0$ 时它必然为 $0$，否则它可以改写成：

$$\begin{align}\sum\limits_{i=1}^t \dbinom{t}{i}(-1)^{i-1} &=\dbinom{t}{0}-\sum\limits_{i=0}^t (-1)^i\dbinom{t}{i}\newline &=1-\sum\limits_{i=0}^t\dbinom{i-t-1}{i}\newline &=1-\dbinom{t+1-t-1}{t}=1 \end{align}$$

那么 $\sum\limits_{i=1}^t\dbinom{t}{i}(-1)^{i-1}=[t> 0]$，从而答案是 $\prod\limits_{\exists x\in S,d|x}g[d]$，剩下只需要求出 $g$，由定义：

$$\begin{align} &f[n]=\prod\limits_{d|n} g[d]\newline \Leftrightarrow \text{ }& \ln f[n]=\sum\limits_{d|n}\ln g[d]\newline \Leftrightarrow \text{ }&\ln g[n]=\sum\limits_{d|n}\mu(n/d)\ln f[d]\newline \Leftrightarrow \text{ }&g[n]=\prod\limits_{d|n}f[d]^{\mu(n/d)} \end{align}$$

即是莫比乌斯反演，那么直接做就是 $O(n(\ln n+\log P)+d(n)|S|)$。

代码：

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int CN = 1e6 + 10;
const int P = 1e9 + 7;
int read(){
    int s = 0, ne = 1; char c = getchar();
    for(;c < '0' || c > '9';c = getchar()) if(c == '-') ne = -1;
    for(;c >= '0' && c <= '9';c = getchar()) s = (s << 1) + (s << 3) + c - '0';
    return s * ne;
}
int add(int x, int y) {return x + y >= P ? x + y - P : x + y;}
int mul(int x, int y) {return 1ll * x * y % P;}
int qp(int a, int b){
    int r = 1;
    for(; b; a = mul(a, a), b >>= 1) if(b & 1) r = mul(r, a);
    return r;
}
int invx(int x) {return qp(x, P - 2);}
int n, f[CN], fi[CN], g[CN], p[CN], mu[CN], md[CN], d[20], alp[20], ans = 1;
bool np[CN], vis[CN];
void sieve(int n){
    np[1] = 1, md[1] = 0, mu[1] = 1;
    for(int i = 2; i <= n; i++){
        if(!np[i]) p[++p[0]] = i, md[i] = i, mu[i] = -1;
        for(int j = 1; i * p[j] <= n && j <= p[0]; j++){
            int x = i * p[j]; np[x] = 1, md[x] = p[j];
            if(i % p[j]) mu[x] = -mu[i]; else break;
        }
    }
    f[1] = 1; for(int i = 2; i <= n; i++) f[i] = add(f[i - 1], f[i - 2]);
    for(int i = 1; i <= n; i++) fi[i] = invx(f[i]);
    for(int i = 1; i <= n; i++) g[i] = 1;
    for(int i = 1; i <= n; i++) for(int j = i; j <= n; j += i){
        if(!mu[j / i]) continue;
        g[j] = mul(g[j], mu[j / i] ^ -1 ? f[i] : fi[i]);
    }
}
void dfs(int i, int fac){
    vis[fac] = 1; if(i > d[0]) return;
    for(int j = 0, k = 1; j <= alp[i]; k *= d[i], j++) dfs(i + 1, fac * k);
}
void work(int x){
    d[0] = 0; int t = x;
    for(; md[t]; t /= md[t]) 
        md[t] ^ d[d[0]] ? d[++d[0]] = md[t], alp[d[0]] = 1 : alp[d[0]]++;
    dfs(1, 1);
}
int main()
{
    // freopen("_in.in", "r", stdin);
    sieve(1000000), n = read(); 
    for(int i = 1; i <= n; i++) work(read());
    for(int i = 1; i <= 1000000; i++) if(vis[i]) ans = mul(ans, g[i]);
    printf("%d\n", ans);
    return 0;
}

又一道栗题

刚开始你有一个数字 $0$，每一秒钟你会随机选择一个 $x\in[0,2^n-1]$，与你手上的数字进行按位或操作，其中选择数字 $i$ 的概率是 $p_i$。问期望多少秒后，你手上的数字变成 $2^n-1$。
$n\le 20$

期望同样可以进行 min-max 容斥，即 $\max$ 代表满足所有限制的操作步数期望，$\min$ 表示满足任意限制的操作步数期望。

那么只需要求给出一个数 $T$，满足 $T$ 中任意一位被覆盖到的期望操作次数。

有一个众所周知的结论：如果重复实验直到成功，并且每次实验成功的概率相同，那么试验次数的期望是每次成功的概率的倒数。证明很简单，设 $x$ 是期望次数，$p$ 是成功概率，由 $x=1+(1-p)x$ 可以解得 $x=1/p$。

那么只需要求出一次成功的概率，即是：

$$\sum\limits_{i\cup T\neq \emptyset}p[i]=1-\sum\limits_{i\subseteq \complement_T}p[i]$$

即是高维前缀和，那么直接做就是 $O(n2^n)$。

代码：

#include<bits/stdc++.h>
using namespace std;
#define DB double
const DB EPS = 1e-10;
int n, B; DB p[1 << 20], e[1 << 20], ans;
int bits(int x) {int r = 0; while(x) r++, x -= x & (-x); return r;}
void work(){
    for(int j = 0; j < n; j++) for(int i = 0; i <= B; i++)
        if((i >> j) & 1) p[i] += p[i ^ (1 << j)];
    for(int i = 0; i <= B; i++) e[i] = 1 - p[B ^ i];
    for(int i = 1; i <= B; i++){
        if(e[i] < EPS) return (void)(puts("INF"));
        e[i] = 1 / e[i];
    }
    for(int i = 1; i <= B; i++) ans += bits(i) & 1 ? e[i] : -e[i];
    printf("%.10lf\n", ans);
}
int main(){
    scanf("%d", &n), B = (1 << n) - 1;
    for(int i = 0; i <= B; i++) scanf("%lf", &p[i]);
    return work(), 0;
}

双一道栗题

给定一棵 $n$ 个结点的树，你从点 $x$ 出发，每次等概率随机选择一条与所在点相邻的边走过去。
有 $q$ 次询问，每次询问给定一个集合 $S$，求如果从 $x$ 出发一直随机游走，直到点集 $S$ 中所有点都至少经过一次的话，期望游走几步。起点视为一开始就被经过了一次，对 $998244353 $ 取模。
$n\le 18, \sum|S|\le 10^7$

min-max 容斥一下，就是求从根出发，到 $T$ 中任意一点的期望步数。设 $f[u]$ 表示从 $u$ 出发的期望步数，显然有：

$$ f[u]=1+\dfrac{1}{deg[u]}(f[fa[u]]+\sum\limits_{v:son[u]}f[v]) $$

特别的，有 $f[u]=0,u\in S$。接下来就套上树上高消那一套，即设 $f[u]=k[u]f[fa[u]]+b[u]$，有：

$$\begin{align} deg[u]f[u]&=deg[u]+f[fa[u]]+f[u]\sum\limits_v{k[v]}+\sum\limits_v{b[v]} \newline \Leftrightarrow f[u]&=\dfrac{1}{deg[u]-\sum k[v]}f[fa[u]]+\dfrac{deg[u]+\sum b[v]}{deg[u]-\sum k[v]}\end{align}$$

也就是 $k[u]=\dfrac{1}{deg[u]-\sum k[v]},b[u]=\dfrac{deg[u]+\sum b[v]}{deg[u]-\sum k[v]}$，我们只保留 $E(S)=f[x]$ 即可，这部分是 $O(n2^n)$。

考虑答案即是 $\sum\limits_{T\subseteq S} (-1)^{|T|-1}E(T)$，即是高维前缀和，那么直接做就是 $O(n2^n)-O(1)$，因此总复杂度 $O(n2^n+\sum|S|)$。

代码：

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int P = 998244353;
int read(){
    int s = 0, ne = 1; char c = getchar();
    for(;c < '0' || c > '9';c = getchar()) if(c == '-') ne = -1;
    for(;c >= '0' && c <= '9';c = getchar()) s = (s << 1) + (s << 3) + c - '0';
    return s * ne;
} 
int add(int x, int y) {return x + y >= P ? x + y - P : x + y;}
int qp(int a, int b){
    int r = 1; 
    while(b){
        if(b & 1) r = 1ll * r * a % P;
        a = 1ll * a * a % P, b >>= 1;
    }
    return r;
}
int invx(int x) {return qp(x, P - 2);}
bool in(int x, int y) {return y & (1 << (x - 1));}
int bits(int x) {int r = 0; while(x) r++, x -= x & (-x); return r;}
int n, q, rt; vector<int> G[20];
int k[20], b[20], f[1 << 18];
void dfs(int u, int p, int S){
    if(in(u, S)) return;
    int deg = G[u].size(), sb = 0, sk = 0, M;
    for(int i = 0; i < deg; i++){
        int v = G[u][i]; if(v == p) continue;
        dfs(v, u, S), sb = add(sb, b[v]), sk = add(sk, k[v]);
    }
    M = add(deg, P - sk), k[u] = invx(M), b[u] = 1ll * k[u] * add(deg, sb) % P;
}
int cal(int S){
    memset(k, 0, sizeof(k)), memset(b, 0, sizeof(b));
    return dfs(rt, 0, S), b[rt];
}
int main()
{
    // freopen("_in.in", "r", stdin);
    n = read(), q = read(), rt = read();
    for(int i = 1; i < n; i++){
        int u = read(), v = read();
        G[u].pb(v), G[v].pb(u);
    }
    for(int S = 1; S < (1 << n); S++){
        f[S] = cal(S);
        f[S] = bits(S) & 1 ? f[S] : add(0, P - f[S]);
    }
    for(int j = 0; j < n; j++) for(int S = 0; S < (1 << n); S++)
        if(S & (1 << j)) f[S] = add(f[S], f[S ^ (1 << j)]);
    while(q--){
        int m = read(), u, S = 0;
        while(m--) u = read() - 1, S |= 1 << u;
        printf("%d\n", f[S]);
    }
    return 0;
}

叒一道栗题

有 $n$ 种原料，每个单位时间会随机生成一种原料。每种原料被生成的概率是不同的，第 $i$ 种原料被生成的概率是 $\frac{p_i}{m}$，其中 $m=\sum p_i$。问收集到任意 $k$ 种原料的期望时间，对 $998244353$ 取模。
$k\le n\le 1000, n-k\le 10, m\le 10^4$

考虑满足任意 $k$ 条限制即是 $k\text{-th}\min$，把它转化成 $(n-k+1)\text{-th}\max$ 来求就可以仿照上例了。以下认为 $k$ 是 $n-k+1$ 来进行推导。

即是求收集到某个集合中，任意一种原料的期望时间。显然这个概率是 $\sum\limits_{i\in T} \dfrac{p_i}{m}$，期望是$\sum\limits_{i\in T} \dfrac{m}{p_i}$，那么答案就是：

$$\sum\limits_{T\neq \emptyset} (-1)^{|T|-k}\dbinom{|T|-1}{k-1}\sum\limits_{i\in T}\dfrac{m}{p_i}$$

直接做是不行的，考虑对 $k$ 和 $\sum p_i$ 分类，即设 $f[i,j,k]$ 表示考虑前 $i$ 个数，当前 $\sum p_i=j$，对 $k$ 求上式得到的和。

考虑转移，如果不选择 $i$，那么 $f[i,j,k]\gets f[i-1,j,k]$。如果选择 $i$，考虑 $j,k$ 同时变化，把组合数拆开，贡献应当是 $-(f[i-1,j-p[i],k]-f[i-1,j-p[i],k-1])$。那么递推式是:

$$ f[i,j,k]=f[i-1,j,k]+f[i-1,j-p[i],k-1]-f[i-1,j-p[i],k] $$

边界是 $f[i,0,0]=1$，那么这样 DP 的复杂度就是 $O(nm(n-k))$。

代码：

#include<bits/stdc++.h>
using namespace std;
const int CN = 1e4 + 10;
const int P = 998244353;
int read(){
    int s = 0, ne = 1; char c = getchar();
    for(;c < '0' || c > '9';c = getchar()) if(c == '-') ne = -1;
    for(;c >= '0' && c <= '9';c = getchar()) s = (s << 1) + (s << 3) + c - '0';
    return s * ne;
}
int add(int x, int y) {return x + y >= P ? x + y - P : x + y;}
int n, K, m, f[CN][20], p[CN], inv[CN];
int main()
{
    // freopen("_in.in", "r", stdin);
    n = 1e4, inv[1] = 1; 
    for(int i = 2; i <= n; i++) inv[i] = 1ll * inv[P % i] * (P - P / i) % P;
    n = read(), K = n - read() + 1, m = read();
    for(int i = 1; i <= n; i++) p[i] = read();
    f[0][0] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = m; j >= p[i]; j--) for(int k = K; k; k--)
            f[j][k] = add(f[j][k], add(f[j - p[i]][k - 1], P - f[j - p[i]][k]));
    }
    int ans = 0;
    for(int j = 1; j <= m; j++) ans = add(ans, 1ll * m * inv[j] % P * f[j][K] % P);
    printf("%d\n", ans);
    return 0; 
}

相关题目

1. 「SDJX2017」第三题
2. 「HAOI2015」按位或
3. 「PKUWC2018」随机游走
4. 「LG-P4707」重返现世