wiki - 算法小站

wiki 主题

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

算法基础搜索数据结构字符串数学图论动态规划计算几何杂项

数学

组合计数

二项式定理

生成函数（一）

FFT

多项式与形式幂级数

同余与模

同余与模的应用

同余与模的概念

特殊的数

斯特林数

斯特林数相关的恒等式

斯特林数的综合应用

FFT的应用

整除分块

min-max容斥

[[ item.c ]]

min-max容斥

## Min-max 容斥原理定义
将一个**全部完成**的问题（max 问题），转化成若干个简单的**至少完成一个**（min 问题）的线性组合

给定一个全序集的有限子集$$S$$，记$$\max(S)$$为集合中的最大值，$$\min(S)$$为集合中的最小值
Min-max 容斥有
```math
\displaystyle
\max(S) = \sum_{\emptyset \neq T \subseteq S} (-1)^{|T| - 1} \min(T) \\
\quad \\
\min(S) = \sum_{\emptyset \neq T \subseteq S} (-1)^{|T| - 1} \max(T)
```
其中$$T$$遍历所有$$S$$的非空子集，$$|T|$$表示子集大小

## 直观理解
容斥原理，$$|A \cup B| = |A| + |B| - |A \cap B|$$
定义集合的并$$\cup$$对应取`max`（最大值涵盖了所有较小的值）
集合的交$$\cap$$对应取`min`（最小值会被包含在所有较大的值中）
这里的**大/小关系**，可以看作是**子集的大小**
取交，那么肯定以大小最小的子集为准，取并呢？大小最大的子集可以吸收其他子集

考虑$$S = \\{x, y\\}, x < y$$
左边`max(S) = y`
右边求和
```bash
|T| = 1，对应集合 {x}, {y}，min{x} = x, min{y} = y，系数 1
|T| = 2，对应集合 {x, y}，min{x, y} = x，系数 -1
和是 x + y - x = y
```
归纳，发现这样正负抵消，只会保留住最大值的贡献

## 证明
不妨假设元素已排序$$x_1 \leqslant x_2 \leqslant \cdots x_n$$，$$\max(S) = x_n$$

现在我们考察$$\sum \min(T)$$，哪些数能作为$$T \subseteq S$$集合中的最大值
以及它们分别被加了多少次

对于$$x_i$$，它能作为最大值，当且仅当$$x_i \in T$$，另外$$T$$中还可以选哪些元素？

$$T \subseteq \\{x\_i, x\_{i+1}, \cdots, x\_{n}\\}$$ （即$$T$$中除了$$x_i$$外还额外选了哪些元素？）
额外选的只能是$$x[i+1\cdots n]$$这$$(n - i)$$个元素，假设说选了$$k$$个
那么子集的大小$$|T| = k+1$$（加上原来的$$x_i$$），对于$$x_i$$，它的**系数**是

```math
\displaystyle
C(x_i) = \sum_{k = 0}^{n - i} \binom{n - i}{k} (-1)^{(k+1) - 1} = \sum_{k}^{n-i} \binom{n - i}{k}(-1)^k
```
右边，当且仅当$$n = i$$时$$= 1$$，其他情况$$= 0$$（实际上相当于二项式$$(1-1)^{n - i}$$展开）
因此右侧的求和结果是$$= 1 \cdot x_n = x_n$$，证毕

## 期望视角下的 Min-max
对恒等式两边取期望
```math
\displaystyle
E[\max(S)] = \sum_{\emptyset \neq T \subseteq S} (-1)^{|T|-1} E(\min(T))
```
**赠券收集问题**
令$$E[\max(S)]$$表示集合$$S$$中所有事件都发生的期望时间（最后一个事件发生的时刻）
因为事件中存在依赖关系，所以计算起来非常麻烦

而$$E[\min(T)]$$表示$$T$$中至少有一个事件发生的期望时间（即$$T$$中最早的事件发生的时间）

如果事件$$i$$发生的概率是$$p\_i$$，并且每一步独立，那么$$T$$中至少有一个事件发生的概率是$$P(T) = \sum\_{i \in T} p\_i$$

这是一个**几何分布**，根据期望公式，$$E[\min(T)] = \dfrac{1}{P(T)}$$

## Min-max 基础应用
### HDU 4336
**[Card Collector](https://acm.hdu.edu.cn/showproblem.php?pid=4336)**
给定`n`种卡片，每包方便面中有一张卡片，其中出现第$$i$$种卡片的概率是$$p\_i$$
有些包里没有卡片，概率是$$1 - \sum\_i p\_i$$
求集齐所有卡片需要购买的期望包数

**算法分析**
记$$X_i$$为获得第$$i$$种卡片需要的时间，目标就是求$$E[\max(X_1, X_2, \cdots X_n)]$$
利用`min-max 容斥`，考虑求
```math
\displaystyle
E[\max(S)] = \sum_{\emptyset \neq T \subseteq S} (-1)^{|T| - 1} E[\min(T)]
```
其中$$E[\min(T)]$$表示第一次获得集合$$T$$中任意一张卡片的期望时间
只要枚举集合$$T$$，单次操作命中集合$$T$$的概率，$$P(T) = \sum\_{i \in T} p_i$$

这是一个**等待时间问题**，符合**几何分布**，期望时间是确定的，$$E = \dfrac{1}{P(T)}$$
特别说明，如果$$\sum p_i = 0, E \to \infty$$，该集合无法被命中

### HAOI 按位或
**[HAOI2015 按位或](https://www.luogu.com.cn/problem/P3175)**
刚开始你有一个数字`0`，每一秒钟你有一个随机生成器，以$$p_i$$的概率生成数$$i$$
你将当前手持的数字与生成的数字进行`or`操作，期望经过多少秒你的数字会变成$$2^n - 1$$

**算法分析**
将每一个二进制位看作一个物品，实际上就是问将所有二进制位都集齐的最短时间
用`min-max`容斥，求出**至少有一个位变成`1`**的期望时间

这是一个几何分布，对于集合$$T$$，实际上`P(T) = 1 - P(T_allzero)`
即求出`T`所有位都保持是`0`的概率

> 考虑`P(T_allzero)`怎么求？

枚举所有的$$T$$（用二进制表示，`1`表示`T`包含了哪些位）
对于$$x = p_i \quad i \in [0, n)$$，$$x \cap T = \emptyset$$，这样的$$x$$才能选

换句话说，$$x$$必须**命中`T`的补集**，需要计算$$\sum p(x \subseteq \text{T 的补集})$$

> 所以$$P(\text{T 所有位都保持 0}) = \sum p(\text{T 的补集})$$

这个求和可以用`SOS`前缀和**预处理**
这样`min-max 容斥`中$$P(T) = 1 - P(T \text{ 所有位都保持 0})$$

根据几何分布，$$E(\min(T)) = \dfrac{1}{P(T)}$$

#### 算法实现
```bash
void solve(int cas) {
    int n;
    cin >> n;

i64 N = 1 << n;
    vector<double> S(N+5, 0.0), P(N+5, 0.0);

for (int i = 0; i < N; i++) cin >> S[i];

auto prework = [&]() -> void {
        for (int i = 0; i < n; i++) {
            for (int mask = 0; mask < N; mask++) {
                if (mask >> i & 1) S[mask] += S[mask ^ (1 << i)];
            }
        }
    };
    prework();

u64 all = N - 1;
    double ans = 0.0;
    for (auto T : all_subset(all)) {
        if (T == 0) continue;
        
        u64 CT = all ^ T;
        P[T] = 1 - S[CT];

int cnt = popcnt(T);
        if (P[T] < eps) {
            cout << "INF\n";
            return;
        }

cnt & 1 ? ans += 1 / P[T] : ans -= 1 / P[T];
    }
    cout << ans << "\n";
}
```

## K-th min-max
收集`n`种卡片，求收集到第`k`种卡片的期望时间，或者在图论中，求第`k`条边被覆盖的期望步数

记`kth-max(S)`表示`S`中第`k`大的元素，`1 表示最大，|S|表示最小`
```math
\displaystyle
\text{kth-max}(S) = \sum_{\emptyset \neq T \subseteq S}(-1)^{|T|-k} \binom{|T|-1}{k-1} \min(T) \quad \\
E[\text{kth-max}(S)] = \sum_{\emptyset \neq T \subseteq S}(-1)^{|T|-k} \binom{|T|-1}{k-1} E[\min(T)]
```
这个公式比基础的公式多了一个组合数系数$$\displaystyle \binom{|T|-1}{k-1}$$
符号判定的基准是$$|T| - k$$，如果$$k = 1$$退化成基准公式$$(-1)^{|T|-1}$$

## 构造性证明
假设集合$$S = \\{x_1, x_2, \cdots, x_n\\}$$并且排序$$x_1 \leqslant x_2 \leqslant \cdots \leqslant x_n$$

我们要证明的是，右边恰好等于$$x\_{n - k + 1}$$

考虑任意元素$$x_r$$，它是$$S$$中第$$n - r + 1$$大的数，$$x_r$$总贡献系数是多少呢？

那么$$x_r$$在集合$$T$$中的充要条件是，$$T$$中除了放一个$$x_r$$，还可以放哪些元素

还可以放$$\subseteq \\{x\_{r+1}, \cdots, x\_{n}\\}$$，那么$$T$$中$$> x\_r$$的元素个数是$$j, |T| = j + 1$$
其中$$j \in [0, n - r]$$，设$$x\_r$$的总系数是$$C(n, r)$$，构造
```math
\displaystyle
C(r, k) = \sum_{j = 0}^{n-r} \binom{n - r}{j} (-1)^{(j+1) - k} \binom{(j+1) - 1}{k-1} \\
\quad \\
C(r, k) = \sum_{j = 0}^{n - r} \binom{n - r}{j} \binom{j}{k-1} (-1)^{j+1-k}
```
用组合恒等式$$\binom{n}{r}\binom{r}{k} = \binom{n}{k} \binom{n - k}{r - k}$$

这里令$$m = n - r$$
```math
\displaystyle
C(r, k) = \binom{m}{k - 1} \sum_{j = k-1}^{m} \binom{m - (k-1)}{j - (k-1)} (-1)^{j - (k - 1)} 
```
注意到右边的求和实际上就是二项展开$$(1- 1)^{m - (k - 1)}$$
当$$m < (k - 1)$$，即$$r > n - k + 1$$，系数显然是`0`
当$$m > (k - 1)$$，即$$r < n - k + 1$$，系数也是`0`
当且仅当$$m = k - 1$$，即$$r = n - k + 1$$时，系数才是`1`

所以右边的值就是$$x\_{n - k + 1}$$

## 系数动态规划
我们利用`DP`来合并具有相同属性$$\sum_i p_i$$的子集的系数（需要符合几何分布）
```math
\displaystyle
E = \sum_T \left( (-1)^{|T|-k} \binom{|T|-1}{k-1} \right) \cdot \dfrac{1}{\sum_{x \in T}p_x}
```
将括号内的部分记为容斥系数，$$f_k(|T|) = (-1)^{|T|-k} \binom{|T|-1}{k - 1}$$

我们枚举每一个可能的概率和$$\sum p_x = S$$，求有多少种方案，并且求出这些方案的系数之和
使得子集的$$p$$值之和是$$S$$

利用组合数的性质$$\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$$
现在求第$$k$$大值的容斥系数，设$$dp(i, j)$$表示考虑前$$i$$个物品，当前选出的子集$$T$$的概率和是$$j$$时
所有可能方案的系数$$f_k(|T|)$$的累加和

似乎行不通，因为$$f_k(|T|)$$依赖于$$|T|$$具体值，但是我们只想知道它的概率和$$j$$，具体是多少我们不关心

**利用递推性**
假设说在$$|T|$$中放入一个新元素，那么系数是怎么变化的？
```math
\displaystyle
(-1)^{|T|-k} \binom{|T|-1}{k-1} \to (-1)^{|T|+1-k}\binom{|T|}{k-1}
```
如果我们记$$g_k(T) = (-1)^{|T|-k} \binom{|T|-1}{k-1}$$

那么$$g\_k(T \cup \\{x\\}) = -g\_k(T) + g\_{k-1}(T)$$，不难发现关于`k`的系数依赖于关于`k-1`的系数
可以递推

### 重返现世
**[P4707 重返现世](https://www.luogu.com.cn/problem/P4707)**
收集`n`种物品，第`i`种物品每次掉落的概率是$$\dfrac{p_i}{m}$$，求收集到`k`种不同物品的期望步数

实际上就是求第$$n - k + 1$$的期望，最先收集的是`min`，最后收集到的是`max`
那么收集到第`k`个，实际上是第$$K = n - k + 1$$大的期望

带入`min-max`计算的`k`，应该是$$K = n - k + 1$$

**算法分析**
围绕**满足条件的概率和，第`k`大**两个条件来设计状态转移方程
令$$dp(S, j)$$表示当前考虑的所有子集中，子集的概率和是$$S$$，对应的第`j`大`min-max`容斥系数的和

其中$$S \in [1,m], j \in [1, k]$$

对应到`kth-min-max`容斥方程中，实际上答案是
```math
\displaystyle
\sum_T coef_k(|T|) \cdot \dfrac{m}{\sum_{x \in T} p_x} = \sum_S dp(S, k) \cdot \dfrac{m}{S}
```
状态转移方程
对于特定的排名$$j$$，当前考虑的子集是$$T$$，对应的概率和是$$S$$

那么$$\displaystyle C_j(T) = (-1)^{|T|-j} \binom{|T|-1}{j-1}$$

假设当前考虑的物品是$$x$$，概率是$$p_x$$

当前的决策
1）不选$$x$$，贡献不变
2）选$$x$$，$$T' = T \cup \\{x\\}, S \to S + p_x$$，$$C_j(T') = (-1)^{|T|+1-j} \binom{|T|}{j - 1}$$

组合恒等式展开
```math
\displaystyle
C_j(T') = (-1)^{|T|+1-j} \left( \binom{|T|-1}{j-1} + \binom{|T|-1}{j-2} \right) \\
\quad \\
= -(-1)^{|T|-j} \binom{|T|-1}{j-1} + (-1)^{|T|-(j-1)} \binom{|T|-1}{(j-1)-1} \\
\quad \\
= -C_j(T) + C_{j-1}(T)
```
状态转移方程如下
```math
\displaystyle
dp(S+p_x, j) \leftarrow dp(S+p_x, j) + (-dp(S, j) + dp(S, j-1))
```
边界条件
对于$$|T| = 1$$，只选一个元素，$$\displaystyle C_k(\\{x\\}) = (-1)^{1-k} \binom{0}{k-1}$$

当$$k = 1$$时，系数是`1`，$$k > 1$$时，系数是`0`

**最佳实践**
初始化$$dp(i, j) = 0$$，但是$$dp(0, 0) = 1$$，当$$T = \emptyset$$，考虑$$T \to T'$$

对于$$|T'| = 1$$的情况，$$C\_j(T') = -C\_j(\emptyset) + C\_{j-1}(\emptyset)$$

如果我们规定$$C\_{0}(\emptyset) = 1$$，并且$$C\_{j > 0}(\emptyset) = 0$$

不难发现对于$$k = 1$$，我们有$$C\_1(T') = -C\_{1}(\emptyset) + C\_{0}(\emptyset) = 0 + 1 = 1$$

恰好满足，对于$$k > 1$$的情况，也有$$C_k(T') = -0 + 0 = 0$$正确

最终的答案是$$\displaystyle \sum_S dp(S, k) \cdot \dfrac{m}{S}$$

> 特别注意

这里`dp`值计算采用背包的滚动数组，$$S$$要倒着`for`

#### 算法实现
```bash
void solve(int cas) {
    int n, K, m;
    cin >> n >> K >> m;

K = n - K + 1;

vector<int> p(n+1, 0);
    for (int i = 1; i <= n; i++) cin >> p[i];

vector<mint> inv(m+10, 0);
    auto table = [&]() -> void {
        inv[1] = 1;
        for (int i = 2; i <= m; i++) {
            inv[i] = (mint)( 1LL * (MOD - MOD / i) * inv[MOD % i].val() % MOD);
        }
    };
    table();

vector dp(m+5, vector<mint>(K+5, 0));
    dp[0][0] = 1;

for (int i = 1; i <= n; i++) {
        for (int S = m; S >= 1; S--) {
            for (int j = 1; j <= K; j++) {

if (S - p[i] < 0) continue;
                dp[S][j] += dp[S - p[i]][j-1] - dp[S - p[i]][j];

}
        }
    }

mint ans = 0;
    for (int S = 0; S <= m; S++) {
        ans += dp[S][K] * mint(m) * inv[S];
    }
    cout << ans << "\n";
}
```
### AtCoder Beginner Contest 242 Ex
**[Ex - Random Painting](https://atcoder.jp/contests/abc242/tasks/abc242_h)**
有`n`个编号`1-n`的格子，一开始都是白色的，给定`m`个球，重复以下操作
1）随机取一个球
2）设取出的球是$$x$$，将$$[l_x, r_x]$$格子全部涂黑
3）放回所取的球

问所有格子都变黑所需要的操作次数的期望值

**算法分析**
这是一个`min-max`容斥问题，假设当前考虑集合$$T$$，记$$D(T)$$为完全和$$T$$不相交的线段的个数
于是$$P(T) = 1 - \dfrac{D(T)}{m}$$，由于是几何分布，$$E[\min(T)] = \dfrac{m}{m - D(T)}$$

根据`min-max 容斥`，$$ans = \sum\_{\emptyset \neq T \subseteq S} (-1)^{|T|-1} \dfrac{m}{m - D(T)}$$

因为$$n \leqslant 400$$，不能暴力，考虑`dp`
`dp`大致的形式是令$$S = D(T)$$，记一下概率和，$$ans = \sum_S dp(?, S) \cdot \dfrac{m}{m - S}$$

> dp 状态设计

令$$dp(i, S)$$表示当前选的集合$$T$$的最右端是$$i$$，并且$$T$$的“漏网之鱼”的个数是$$S$$，此时的`coef`系数和

对于每个位置$$i$$，我们要考虑$$T$$中上一个位置，即$$T'$$对应的最优端点
上一个位置可能是$$j \in [0, i-1]$$，枚举$$j$$，那么$$T'$$最右端点是$$j$$对应的“漏网之鱼”个数是少呢？

到$$i$$为止漏网之鱼个数是$$S$$，那么到$$j$$，漏网之鱼个数要看$$[j+1, i-1]$$中线段的个数

区间线段的个数完全可以**二维前缀和预处理**
```bash
for i 从大到小，for j 从小到大
	cnt(i, j) += cnt(i+1, j) + cnt(i, j-1) - cnt(i+1, j-1)
```
所以有转移$$dp(i, S) += -\sum\_{j \in [0, i-1]}dp(j, S - cnt(j+1, i-1))$$

> 统计答案

枚举$$T$$最后的元素**停在哪里**，同时还要枚举$$S$$
枚举$$T$$最后的元素停止的位置$$j \in [1, n]$$，注意到尾巴$$[j+1\cdots n]$$这段漏网之鱼
是**没有被贡献到**`dp`状态中的
```bash
for 对于每个漏网之鱼数量 S
	for 集合 T 中停下的位置 j
		真正对 dp 状态系数有贡献的漏网之鱼数量是 S - cnt(j+1, n)
		coef[S] += dp(j, S - cnt(j+1, n))
```

最后的答案就是
```bash
for 每一个 S
    ans += coef[S] * m / (m - S)
```

如果硬要用`dp(i, S)`，枚举`i, S`来统计答案
```bash
for i = T 最后停下的位置， for S = [1...i] 漏网之鱼的数量
	ans += dp(i, S) * m / (m - ([i+1...n] 的线段数量) )
	// 记得加上 [i+1...n]，他们都是漏网之鱼！
```

#### 算法实现
```bash
void solve(int cas) {
    int n, m;
    cin >> n >> m;

using pr = pair<int, int>;
    vector<pr> seg;

for (int i = 0; i < m; i++) {
        int li, ri;
        cin >> li >> ri;
        seg.emplace_back(li, ri);
    }

vector cnt(n+5, vector<int>(n+5, 0));
    for (auto [l, r] : seg) {
        cnt[l][r] += 1;
    }

for (int i = n; i >= 1; i--) {
        for (int j = 1; j <= n; j++) {
            cnt[i][j] += cnt[i+1][j] + cnt[i][j-1] - cnt[i+1][j-1];
        }
    }

vector dp(n+5, vector<mint>(m+5, 0));
    dp[0][0] = mint(-1);

for (int i = 0; i <= n; i++) {
        for (int S = 0; S <= m; S++) {
            for (int j = 0; j < i; j++) {
                auto ns = S - cnt[j+1][i-1];
                if (ns < 0) continue;
                dp[i][S] += -dp[j][ns];
            }
        }
    }

mint ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int S = 0; S <= m; S++) {
            if (dp[i][S].val() == 0) continue;

int totS = S + cnt[i+1][n];
            ans += dp[i][S] * mint(m) / mint(m - totS);
        }
    }

cout << ans << "\n";
}
```
## 尾和公式
一些问题中，我们常常需要处理**还需要抽多少次，等待时间**
比如，我们记需要抽$$k$$次，才能让$$T$$中的某个元素达到目标

那么抽取次数的期望是$$\displaystyle E[X] = \sum\_{k = 0}^{+\infty} kp(X = k)$$
其中$$X = k$$表示抽了`k`次之后，恰好让其中某个元素达成目标

$$E[X] =P(X=1)$$

$$+ P(X=2) + P(X=2)$$

$$+ P(X=3) + P(X=3) + P(X=3)$$

$$+ P(X=4) + P(X=4) + P(X=4) + P(X=4)$$

$$+ \cdots$$ 
从而我们有
```math
\displaystyle
E[x] = P(x > 0) + P(x > 1) + P(x > 2) + \cdots
```

换句话说，抽取多少次，才能让集合$$T$$中的某个元素命中目标呢？抽取次数的期望是
```math
\displaystyle
E[X] = \sum_{k = 0}^{+\infty} P(X > k)
```
其中$$P(X > k)$$意思是，抽取$$k$$次之后，依然没有任何一个元素命中目标

## wald 等式
当你在对一系列随机变量求和时，如果“求和的项数”本身也是个随机变量，该怎么算期望？

假设有一个随机变量序列$$\\{X_1, X_2, \cdots, X_n\\}$$并且是独立同分布的
也就是说他们互相不影响，服从同一个概率分布，他们的期望是$$E[X_1]$$

> 什么是独立同分布？常常见于什么样的场景？

比如说有一个集合$$S$$，包含所有的英雄
但我们想要的英雄需要抽卡命中，想要的英雄的集合是$$T \subseteq S$$
那这个抽卡的过程，**按是否抽中**$$T$$**中的元素，划分成一段一段的**

那么这样的抽卡序列如下所示
```bash
外，外，T，外，T，T
```
定义$$X_i$$表示为了获得第$$i$$次**有效抽卡**（抽中的元素$$\in T$$）
我们需要的抽卡次数（包括前面若干段抽不中的，和最后一张抽中的）

那么$$X_1 = 3$$（`2`张废卡，接着拿到第`1`张`T`卡）
同理$$X_2 = 2$$（`1`张菲卡，接着拿到第`2`张`T`卡）

那么这个问题中，我们总共的抽卡次数是
```math
tot = X_1 + X_2 + \cdots + X_N = \sum_{i = 1}^{N} X_i
```

此时$$X_1, X_2, \cdots X_N$$是独立同分布的
为什么呢？因为每开始一段**寻找下一个在`T`中的元素的时候**，面对的抽卡池都是一样的

每抽出一张卡，它是`T`中的元素的概率始终是
```math
\displaystyle
p = \dfrac{\sum_{i \in T} a_i}{\sum_{i = 1}^{N} a_i}
```

因此，每一个$$X_i$$都服从一个**几何分布**，表示的意义是，为了获得第一次成功，所需要的实验次数
```math
E[X_i] = \dfrac{1}{p} = \dfrac{\sum_{i = 1}^{N} a_i}{\sum_{i \in T} a_i}
```

> 停时

停时，意味着你决定在第$$n$$步停下来，这个决定只能基于第$$n$$步以及之前发生的事情
绝不能预知未来
在上面的例子中，$$E[tot] = E[\sum\_{i = 1}^{N}X\_i]$$

决定$$N$$具体有多大（抽多少张有效卡才能结束），仅仅取决于我们抽出来的$$T$$卡**具体是谁**
抽多少张我们不关心，也不关心两张$$T$$卡之间隔了多少张废卡，也就是说我们不关心$$X_i$$具体多大

> 瓦尔德等式

当$$X_i$$**独立同分布**，并且$$N$$是**停时**的
```math
\displaystyle
E\left( \sum_{i = 1}^{N} X_i \right) = E(X_i)E(N)
```

> 证明如下
定义指示变量$$I$$，$$I_i = 1$$表示第$$i$$步或者之后才停止，$$N \geqslant i$$，第$$i$$步实际上发生了
$$I_i = 0$$表示在第$$i$$步之前就已经停止了，$$N < i$$，第$$i$$步实际上未发生

> 这样就有
```math
\displaystyle
\sum_{i = 1}^{N} X_i = \sum_{i = 1}^{+\infty} X_i I_i
```
根据期望的线性性质
```math
\displaystyle
E\left( \sum_{i = 1}^{N} X_i \right) = E\left( \sum_{i = 1}^{+\infty} X_i I_i \right) = \sum_{i = 1}^{+\infty} E(X_i)E(I_i) \\
\quad \\
= E(X_i) \sum_{i = 1}^{+\infty} E(I_i) = E(X_i) \sum_{i = 1}^{+\infty} P(N \geqslant i)
```
而注意到$$\sum\_{i = 1}^{+\infty} P(N \geqslant i) = \sum\_{i = 0}^{+\infty} P(N > i) = E(N)$$

> 这一步是根据尾和公式，综上所述，证毕

### 几何分布，步数放大
给定一些数（集合$$S$$），但我们只需要特定的几个（子集$$T \subseteq S$$）
我们需要反复抽卡，抽卡必须命中$$T$$一定次数，才结束抽卡

类似这样的问题，都可以引入**Wald 等式**来求解，$$E(T) = E(N) \cdot E(X_i)$$

1）$$T$$表示**实际的总次数**，因为我们每次抽卡不可能总是抽到$$T$$中的元素
可能抽到一些废卡

2）$$N$$表示**有效卡总数**，你在达成目标的时候，手里有多少张$$\in T$$的有效卡

3）$$X_i$$表示**单次成本**，在实际抽卡中，平均抽多少次才能够得到一张$$\in T$$的**有效卡**

在实际分析的时候，$$E[X_i]$$往往符合几何分布或者其他分布，是很好求的
我们考虑的是如何求出$$E(N)$$

在分析的时候，$$E(N)$$按照尾和公式去求，注意这里的$$N$$实际上代表的是**有效卡**的个数
也就是说，$$X_1 + X_2 + \cdots X_N$$，我们要命中集合$$N$$次

实际上，$$E(N) = \sum\_{k = 0}^{+\infty} P(N > k)$$

我们枚举每一个$$k$$，$$P(N > k)$$表示，**我们手中已经有了$$k$$张有效卡，但是目标依然没有达成**的概率
这个目标没有达成，往往是我们希望凑齐$$T$$中，第$$i$$种类的卡片要$$b_i$$张，这个要求没有达成

单算概率也很容易计算

> 类似这样的问题，算法流程如下

第一步，只考虑在目标集合$$T$$中抽卡，抽卡$$k$$次，枚举这个合法的$$k$$，计算
```math
E(\text{在集合 } T \text{ 内部抽卡达到目标的期望次数}) = \sum_{k} P(\text{抽了 } k \text{ 次仍然没有任何一个元素达到目标的概率})
```
上面求出的结果不妨记为$$E_T$$

第二步，引入步数放大
第一步我们算出了只在$$T$$中抽卡得到的期望次数，但现实是，我们不可能每次抽卡都会命中$$T$$
如果不命中会产生一些废卡，根据**几何分布**的性质

平均要抽$$E(\text{命中 } T ) =  \dfrac{1}{P(T)}$$次，**才会产生一次命中**

也就是说，达成目的需要在$$T$$中抽卡$$E_T$$次，实际上意味着**现实中我们要产生**$$E_T$$**次命中**
而一次命中对应现实中抽卡$$E(\text{命中 } T)$$次，那么$$E_T$$次命中呢？

现实需要一共抽卡$$E = E_T \cdot E(\text{命中 } T) = E_T \dfrac{1}{P(T)}$$次

## AtCoder Grand Contest 038
### E
**[E - Gachapon](https://atcoder.jp/contests/agc038/tasks/agc038_e)**
给定一个随机数生成器，它会生成$$0 \sim n - 1$$之间的整数
每个整数被生成的概率用$$A[0 \cdots n - 1]$$给出，整数$$i \in [0, n-1]$$被生成的概率是$$A_i / S$$

其中$$S = \sum\_{i = 0}^{n-1} A_i$$，每次生成随机数是独立进行的
你需要不断生成随机数，直到满足条件，对所有的$$0 \leqslant i \leqslant n - 1$$
随机数生成$$i$$的次数$$\geqslant B_i$$次
求操作的期望次数

**算法分析**
这个问题的做法比较好想，是一个`min-max 容斥`
如果$$i$$被生成的次数$$\geqslant B_i$$，我们称$$i$$这个元素是被满足的，那么
```math
\displaystyle
E(\max S) = \sum_{T \subseteq S} (-1)^{|T|-1} E(\min T)
```
其中$$\max S$$指的是$$S$$中最后一个元素被满足的时间，$$\min T$$指的是集合$$T$$中第一次有元素被满足的时间

> 考虑对于子集$$T$$，先只在$$T$$中抽取

1）$$T$$表示当前枚举的子集$$\\{c\_{x1}, c\_{x2}, \cdots, c\_{xt}\\}$$

2）$$c_x$$表示$$x \in T$$，$$x$$被抽取的次数

3）$$k = \sum\_{x \in T}c_x$$

以上必须满足$$\begin{cases} \sum\_{x \in T}c_x = k \\\ 0 \leqslant c\_x < B_x \end{cases}$$

4）$$Sa = \sum\_{i = 0}^{n-1}A\_i, \quad Ta = \sum\_{x \in T} A_x$$

只在$$T$$中抽取，$$E(\text{仅在 T 中抽，达到目标}) = E\_T = \sum\_{k = 0}^{+\infty} P(N > k)$$
其中$$P(N > k) = P(\\{c_x\\})$$表示**在`T`中抽了**$$k$$**张目标卡**仍然没达到目标的概率

其中$$k$$分布在$$\\{c\_{x1}, c\_{x2}, \cdots, c\_{xt}\\}$$中，满足$$0 \leqslant k < \sum\_{x \in T}(B_x - 1)$$

另外，$$0 \leqslant c\_x < B\_x, \quad  \sum\_{x \in T} c\_x = k$$

> 对于特定的$$k = c\_{x1} + c\_{x2} + \cdots + c\_{xt}$$，符合**多项分布**
其中下标是$$x$$的物品，被抽到的概率是$$p_x = A_x / Ta$$（注意此时我们只考虑在$$T$$中抽）

```math
\displaystyle
P(\text{特定的 } c_x \text{ 组合}) = \binom{k}{c_{x1}, c_{x2}, \cdots, c_{xt}} \prod_{x \in T} p_x^{c_x} \\
\quad \\
= \dfrac{k!}{\prod_{x \in T} c_x !} \prod_{x \in T} \left(\dfrac{A_x}{Ta} \right)^{c_x} = \dfrac{k!}{Ta^k} \prod_{x \in T} \dfrac{A_x^{c_x}}{c_x!}
```
而$$c\_{x1}, c\_{x2}, \cdots, c\_{xt}$$我们还需要枚举

> 进一步地

```math
\displaystyle
P(\text{特定的 } k) = \dfrac{k!}{Ta^k} \sum_{c_x, \sum_x c_x = k} \prod_{x \in T} \dfrac{A_x^{c_x}}{c_x!}
```
那么我们有
```math
\displaystyle
E(\text{仅在 } T \text{ 中抽取}) = \sum_{k = 0}^{+\infty} P(N > k) \\
\quad \\
= \sum_{k = 0}^{+\infty} \left( \dfrac{k!}{Ta^k} \sum_{c_x, \sum c_x = k} \prod_{x \in T} \dfrac{A_x^{c_x}}{c_x!} \right)
```
> 但实际上，我们不可能每一次抽取都命中$$T$$，还可能产生废卡
我们需要按照**几何分布**进行**步数放大**
放大的比率，实际上就是考虑**抽多少次才会有一次命中？**，$$P = \dfrac{Ta}{Sa}$$
从而$$E = 1/P = \dfrac{Sa}{Ta}$$

```math
\displaystyle
E(\min T) = Sa \cdot \sum_{k = 0}^{+\infty} \left( \dfrac{k!}{Ta^{k+1}} \sum_{x \in T, \sum c_x = k} \prod \dfrac{A_x^{c_x}}{c_x!} \right)
```
最后，答案是
```math
\displaystyle
ans = E(\max T) = Sa \sum_{T \subseteq S}(-1)^{|T|-1} E(\min T)
```

不可能枚举每个子集的，注意到之前的分析，哪些和$$T$$相关的？

我们枚举了特定的$$\displaystyle k = \sum\_{x \in T} c\_x$$，并且$$\displaystyle Ta = \sum\_{x \in T} A_x$$

不难发现，$$k$$可能的取值$$[0 \cdots \sum\_{i = 0}^{n-1} (B_i - 1)]$$

而$$Ta = \sum\_{x \in T} A\_x$$，可能的取值呢？$$[0\cdots \sum\_{i = 0}^{n-1}  A_i]$$

这样，考虑每个位置的贡献，答案可以写成
```math
\displaystyle
ans = E(\max S) = Sa \sum_{T \subseteq S} (-1)^{|T|-1} \sum_{k = 0}^{\sum (B_i - 1)} \dfrac{k!}{Ta^{k+1}} \prod_{x \in T} \dfrac{A_x^{c_x}}{c_x!}
```
> 怎么计算

注意到，$$k = \sum\_{x \in T} c\_x, Ta = \sum\_{x \in T} A\_x$$，这是可以**背包的**

用$$dp(k, ta)$$表示系数，即
```math
\displaystyle
dp(k, ta) = \sum_{\sum_{x \in T} A_x = ta} \sum_{\sum_{x \in T} c_x = k} (-1)^{|T|-1} \cdot \prod_{x\in T} \dfrac{A_x^{c_x}}{c_x!}
```

考虑当前位置，**是否放入**$$T$$中，**放几个**？
我们还需要枚举当前位置$$i$$，**放几个进**$$T$$中，$$c_i \in [0, \min(k, B_i - 1)]$$

这样有转移
```math
\displaystyle
ndp(k, ta) = dp(k, ta) - \sum_{c_i = 0}^{\min(k, B_i - 1)} dp(k - c_i, ta - A_i) \cdot \dfrac{A_i^{c_i}}{c_i !}
```
初始状态$$dp(0, 0) = -1$$，最终的答案
枚举所有可能的$$k, ta$$
```math
\displaystyle
ans += Sa \cdot dp(k, ta) \cdot \dfrac{k!}{Ta^{k+1}}
```
> 坑点，dp 枚举的时候，$$ci \in [0, b_i - 1]$$，必须从`0`开始而不是从`1`开始
不放进集合$$T$$ 和 放进集合$$T$$但抽了`0`次 ($$c_i = 0$$) 是完全不同的概念

> 我们计算期望是用$$\sum P(N > k)$$来求的，即抽了`k`次还没有达到目的的概率
那么对于$$x$$，你放进集合$$T$$，但是被命中`0`次，当然也算没有达到目的，也要被统计进去！

#### 算法实现
```bash
void solve(int cas) {
    int sa = accumulate(A.begin()+1, A.end(), 0);
    int upk = accumulate(B.begin()+1, B.end(), 0, [](int acc, int val) { return acc + val - 1; });

vector dp(upk+5, vector<mint>(sa+5, 0));
    dp[0][0] = mint(-1);

for (int i = 1; i <= n; i++) {
        auto ndp = dp;
        ndp.assign(upk+5, vector<mint>(sa+5, 0));

for (int k = 0; k <= upk; k++) {
            for (int ta = 0; ta <= sa; ta++) {
                ndp[k][ta] = dp[k][ta];

// c[i] -> T, c[i] = [0, B[i]-1]
                for (int ci = 0; ci <= B[i]-1; ci++) {
                    if (not (k - ci >= 0 and ta - A[i] >= 0)) continue;

ndp[k][ta] -= dp[k - ci][ta - A[i]] * pw[A[i]][ci] * comb.invfac(ci);
                }
            }
        }

dp = ndp;
    }

mint ans = 0;
    for (int k = 0; k <= upk; k++) {
        for (int ta = 0; ta <= sa; ta++) {
            ans += mint(sa) * dp[k][ta] * comb.fac(k) / pw[ta][k+1];
        }
    }
    cout << ans << "\n";
}
```
## 树上min-max
**[PKUWC2018 随机游走](https://www.luogu.com.cn/problem/P5643)**
给定`n`个节点的树，从根节点出发随机游走，每次等概率移动到相邻节点
给定一个集合$$S \subset V$$，求访问完所有节点所需要的**期望时间**，$$n \leqslant 18$$，会有多次询问
每次询问给定不同的$$S$$

**算法分析**
```math
\displaystyle
E[\max S] = \sum_{T \subseteq S} (-1)^{|T|-1} E[\min T]
```
可以枚举$$T \subseteq S$$，$$E(\min T)$$表示访问$$T$$中**任意一个节点的期望时间**

用$$dp(u)$$表示从$$u$$出发，到达$$T$$中任意一个节点的期望时间
1）如果$$u \in T$$，那么$$dp(u) = 0$$

2）否则的话，$$dp(u) = 1 + \dfrac{1}{deg(u)} \sum\_{v }dp(v)$$

但比较尴尬的是，这里存在$$u$$要从$$pa_u$$转移过来，这就有后效性了，解决办法是高斯消元
如果高斯消元，复杂度不可接受

> 树的结构比较简单，可以用**树上待定系数法**

怎么做呢？$$dp(u) = K_u \cdot dp(pa(u)) + B_u$$，其中$$(K_u, B_u)$$为待定系数
实际上，令$$d_u$$表示$$u$$的度数

```math
\displaystyle
dp(u) = 1 + \dfrac{1}{d_u} (dp(pa_u) + \sum dp(v))
```
而根据待定系数，$$dp(v) = K_v \cdot dp(u) + \sum B_v$$
```math
\displaystyle
dp(u) = 1 + \dfrac{1}{d_u} \left( dp(pa_u) + \sum (K_v \cdot dp_u + B_v) \right) \\
\quad \\
dp(u) = \dfrac{1}{d_u - \sum K_v} dp(pa_u) + \dfrac{d_u + \sum B_v}{d_u - \sum K_v}
```
对比$$dp(u) = K_u \cdot dp(pa_u) + B_u$$，我们有
```math
\displaystyle
\begin{cases}
K_u = \dfrac{1}{d_u - \sum K_v} \\
\quad \\
B_u = \dfrac{d_u + \sum B_v}{d_u - \sum K_v}
\end{cases}
```
若$$u \in T$$，$$K_u = B_u = 0$$
否则自底向上更新，叶子节点$$v:\quad dp(v) = dp(u) + 1$$，满足$$K_v = B_v = 1$$
实际上叶子节点的$$d_v = 1$$，上述表达式也是满足边界条件的

根节点若$$\notin T$$，就是$$dp(x) = B_x$$

> 查询，查询是若干个集合的，给出$$S$$，需要$$O(1)$$查询$$E(\max S)$$

这个也好办，$$E(\max S) = \sum\_{T \subseteq S} (-1)^{|T|-1} E(\min T)$$

其中我们可以$$2^n$$枚举每一个可能的$$T$$
根节点是给定的$$x$$，可以`dfs`求出，如果$$x \in T$$，$$ans = 0$$
否则，$$ans = dp(x) = B_x$$

上述的`ans`就是`mask`对应的答案，根据`popcount(mask)`，来考虑要不要加`-`号
结果存在`g[mask]`中

然后用**高维前缀和**，枚举每一个`mask = S`，看每一位，答案用`f[mask]`来维护
如果`mask >> i & 1`，`f[mask] += f[mask ^ (1 << i)]`

高维前缀和，实际上就完成了$$E(\max S) = \sum (-1)^{|T|-1} E(\max T)$$的操作
这样就可以$$O(1)$$查询了

### 算法实现
```bash
void solve(int cas) {
    int N = 1 << n;
    vector<mint> f(N+5, 0);

auto calc = [&](int mask) -> mint {
        vector<mint> K(n+5, 0), B(n+5, 0);

auto dfs = [&](this auto &&self, int u, int fa) -> void {
            if (mask >> u & 1) {
                K[u] = B[u] = 0;
                return;
            }

mint sumk = 0, sumb = 0;
            mint du = g[u].size();

for (auto v : g[u]) {
                if (v == fa) continue;
                self(v, u);

sumk += K[v], sumb += B[v];
            }

K[u] = mint(1) / mint( du - sumk );
            B[u] = (du + sumb) / (du - sumk);
        };
        dfs(x, -1);

return (mask >> x & 1) ? 0 : B[x];
    };

for (int mask = 1; mask < N; mask++) {
        f[mask] = calc(mask);
        if (popcnt(mask) % 2 == 0) f[mask] = -f[mask];
    }
	// SOS dp
    for (int u = 0; u < n; u++) {
        for (int mask = 0; mask < N; mask++) {
            if (mask >> u & 1) {
                f[mask] += f[mask ^ (1 << u)];
            }
        }
    }
}
```

看完文章有啥想法

算法小站

wiki 主题

数学

min-max容斥

目录