ABC242Ex

虽然是 ABC，质量、难度还是不错的（考场上没想到）。

题意：给定 $m$ 个区间，每次随机选择一个区间，问期望多少次将 $[1, n]$ 全部覆盖。$n, m\leq 400$。

拆开每一位，相当于是 $E(\max t_i)$，$\max$ 的期望似乎很不好求，我们考虑 min-max 容斥。

$$E(\max_{i\in T} a_i) = \sum_{S\subseteq T} (-1) ^ {|S| + 1}E(\min_{i\in S} a_i)$$

一个集合的 $\min$ 是好求的，我们先求出与之有交的区间个数 $x$，那么选到 $x$ 中的任意一个都是合法的，那么期望显然是 $\dfrac mx$。

直接暴力枚举所有集合显然是不行的，我们考虑前面集合中都 $\subseteq \{1, 2, \dots, i - 1\}$在所有集合中加入 $i$，看需要维护什么。首先我们需要维护新加入 $i$ 后区间的个数，容斥系数直接每次加入元素时乘 -1 即可。维护区间个数需要我们维护出上一个选的数 $ls$，这样 $l\in [ls + 1, i], r\in [i, n]$ 的区间就是新加入的。容易发现这是对的。

于是我们需要维护的就是 $ls$ 表示上一个选的数，$cnt$ 表示有交的区间。状态数为 $O(nm)$，转移为 $O(n)$，总复杂度 $O(n ^ 2m)$。

期望 max/min 可以互相转化。

int main()
{
	f[0][0] = Mod - 1; // last position i, j intervals
	int res = 0;
	for (int i = 0; i <= n; ++ i)
		for (int j = 0; j <= m; ++ j) {
			if (!f[i][j]) continue;
			res = (res + (LL) m * qpow(j) % Mod * f[i][j]) % Mod;
			for (int to = i + 1; to <= n; ++ to)
				adj(f[to][j + cnt[i][to]] -= f[i][j]);
		}
	std::cout << res << std::endl;
}