求期望时比较好用

min-max容斥

式子

先把式子推出来

设 $\max(S), \min(S)$ 表示集合 $S$ 的最大/最小值，我们现在要求 $\max(S)$ ，考虑转化为求 $\min$ ，设：
$$
\max(S) = \sum_{T \subset S \wedge T \ne \varnothing} f(\mid T \mid) \min(T)
$$
这里 $f(x)$ 是容斥系数，现在来求 $f(x)$ ，考虑第 $k$ 大的数，它会被统计的次数为：
$$
\sum_{i = 0}^{k - 1} \binom{k - 1}{i} f(i + 1)
$$
就是 $k - 1$ 个比它大的数构成的集合再加它一个数

那么，由于我们要最大的数，它的系数显然为 $1$ ，有：
$$
\begin{aligned}
& [k == 1] = \sum_{i = 0}^{k - 1} \binom{k - 1}{i} f(i + 1) & (1)
\end{aligned}
$$
考虑到二项式反演：
$$
f(x) = \sum_{i = 0}^{x} \binom{x}{i} g(i) \Leftrightarrow g(x) = \sum_{i = 0}^{x} (-1)^{x - i} \binom{x}{i} f(i)
$$
把 $(1)$ 变形为：
$$
\begin{aligned}[]
[k == 0] &= \sum_{i = 0}^{k} \binom{k}{i} f(i + 1) \\
f(x + 1) &= \sum_{i = 0}^{x} (-1)^{x - i} \binom{x}{i} [i == 0] \\
f(x + 1) &= (-1)^{x} \\
f(x) &= (-1)^{x - 1} \\
\end{aligned}
$$
于是，我们就得到 min-max 容斥的式子：
$$
\max(S) = \sum_{T \subseteq S} (-1)^{\mid T \mid - 1} \min(T)
$$
同理有：
$$
\min(S) = \sum_{T \subseteq S} (-1)^{\mid T \mid -1} \max(T)
$$
我们就把求 $\max$ 和求 $\min$ 联合了，而更令人开心的是，上式对于期望任然成立

例题

不做题是不知道怎么用的，来看这个：

按位或

先直接套上 min-max ，设 $\max(S)$ 表示“集合 $S$ 中每个元素期望出现时间的最大值（其实就是 $S$ 中最晚出现的元素期望出现时间）”，$\min(S)$ 类似，那么有 $\max(S) = \sum_{T \subseteq S} (-1)^{\mid T \mid - 1} \min(T)$ ，问题变成求 $\min(T)$ ，显然任意一位出现即可，有 $\min(T) = \frac{1}{\sum_{G \cap T \ne \varnothing} p[G]}$

求交不容易，考虑求无交，即求 $\sum_{G \cap T = \varnothing} p[G]$ ，显然所有 $G$ 都是 $T$ 的补集的子集，子集和可以做 FWT ，考虑 FWT_or 的式子 $f’(i) = \sum_{i = i | j} f(j)$ ，发现 $f’(i)$ 就是 $i$ 的子集和，总时间 $O(2^n n)$ ，一个需要注意的点是 $T \subseteq S$ ，故不包含 $T = \varnothing$

#include <bits/stdc++.h>
using DB = double;
const int NN = (1 << 20) + 100;
const DB eps = 1e-10;
int n, nn, ct[NN];
DB p[NN], ans;
void fwt_or(DB x[], int len)
{
    for (int i = 2; i <= len; i <<= 1)
        for (int mid = i >> 1, j = 0; j < len; j += i)
            for (int k = j; k < j + mid; ++k) x[k + mid] += x[k];
}
int main()
{
    scanf("%d", &n);
    nn = (1 << n);
    for (int i = 0; i < nn; ++i) scanf("%lf", &p[i]);
    for (int i = 1; i < nn; ++i) ct[i] = ct[i >> 1] + (i & 1);
    fwt_or(p, nn);
    for (int i = 1; i < nn; ++i) 
        if ((1 - p[(nn - 1) ^ i]) > eps) ans += DB((ct[i] & 1 ? 1 : -1)) / (1 - p[(nn - 1) ^ i]); //这里由于是ct-1所以反过来
        else return puts("INF"), 0;
    printf("%.10lf\n", ans);
    return 0;
}

推广

如果不是最大，而是第 $k$ 大，不妨记它为 $kmax(S)$ ，同样设容斥系数：
$$
kmax(S) = \sum_{T \subseteq S} f(\mid T \mid) \min(T)
$$
考虑第 $k$ 大的数，它会被统计的次数任然为：
$$
\sum_{i = 0}^{k - 1} \binom{k - 1}{i} f(i + 1)
$$
有：
$$
[x == k - 1] = \sum_{i = 0}^{x} \binom{x}{i} f(i + 1)
$$
二项式反演：
$$
\begin{aligned}
f(x + 1) &= \sum_{i = 0}^{x} (-1)^{x - (k - 1)} \binom{x}{i} [i == k - 1] \\
f(x + 1) &= (-1)^{x - (k - 1)} \binom{x}{k - 1} \\
f(x) &= (-1)^{x - k} \binom{x - 1}{k - 1}
\end{aligned}
$$
综上：
$$
kmax(S) = \sum_{T \subseteq S} (-1)^{\mid T \mid - k} \binom{\mid T \mid - 1}{k - 1} \min(T)
$$
而如果要求第 $k$ 小，就是求第 $n - k + 1$ 大

例题

重返现世

类似上题，设 $S$ 是获得的材料集合，每个元素的权就是期望获得时间，同时设 $U$ 是全集，那么，我们要求：
$$
kmin(U)
$$
即第 $k$ 小，考虑到 $n - k$ 比较小，以及我们只有 $kmax$ 的式子，所以，令 $k = n - k + 1$ ，那么我们就要求：
$$
kmax(U)
$$
套式子：
$$
kmax(U) = \sum_{S \subseteq U} (-1)^{\mid S \mid - k} \binom{\mid S \mid - 1}{k - 1} \min(S)
$$
发现 $\min(S) = \frac{m}{\sum_{i \in S} p_i}$ 比较好求，于是，我们有了一个 $O(2^n n)$ 的东西

现在考虑 dp （别问怎么想到的）， $m$ 和转化后的 $k$ 不大，直接给它们个一维，设 $d[k][i][j]$ 表示“要求第 $k$ 大，当前考虑第 $i$ 个元素， $\sum_{i \in S} p_i = j$ 的时候 $\min(S)$ 的系数“

状态有了，考虑转移，每个点要么选要么不选，不选直接继承即可，下面考虑选，结论是：
$$
d[k][i][j] = d[k - 1][i - 1][j - p_i] - d[k][i - 1][j - p_i]
$$
意思是：当我选了一个数后， $\mid S \mid$ 会 $+ 1$ ，看式子， $(-1)^{\mid S \mid - k}$ 和 $\binom{\mid S \mid - 1}{k - 1}$ ，第一个好搞，对于第二个，我们有 $\binom{n}{m} = \binom{n - 1}{m} + \binom{n - 1}{m - 1}$ ，即得转移方程

最后一个麻烦是边界

但凡有点良心的出题人 dp 边界都是 $1/0$ 之类的吧？但这个题不，因为我们要保证 $\mid S \mid = k$ 的贡献为 $1$ ，而 $\mid S \mid < k$ 的贡献为 $0$ ，所以应该是 $d[0][0][0] = 0, d[k][0][0] = -1$

打的时候类似背包压掉 $i$ ，时间 $O(nmk)$ ，空间 $O(mk)$ （这里的 $k$ 是转化后的）

#include <bits/stdc++.h>
using LL = long long;
const int K = 10 + 5, N = 1e3 + 100, M = 1e4 + 100, P = 998244353;
int n, s, m, iv[M], ans, p[N], d[K][M];
void adj(int &x){ x += (x >> 31) & P; }
int main()
{
    scanf("%d %d %d", &n, &s, &m);
    s = n - s + 1;
    for (int i = 1; i <= n; ++i) scanf("%d", &p[i]);
    iv[1] = 1;
    for (int i = 2; i <= m; ++i) iv[i] = iv[P % i] * LL(P - P / i) % P;
    for (int i = 1; i <= s; ++i) d[i][0] = -1;
    for (int i = 1; i <= n; ++i)
        for (int j = m; j >= p[i]; --j)
            for (int k = s; k; --k)
            {
                adj(d[k][j] += d[k - 1][j - p[i]] - P);
                adj(d[k][j] -= d[k][j - p[i]]);
            }
    for (int i = 1; i <= m; ++i) adj(ans += LL(d[s][i]) * iv[i] % P - P);
    printf("%d\n", LL(ans) * m % P);
    return 0;
}