考虑 Min-Max 容斥,$\min(S)$ 表示至少一个从 $s$ 走到至少一个属于集合 $S$ 的点的期望时间。

用 $f(i, S)$ 表示集合 $S$ 下 $i$ 到任意 $u \in S$ 的期望时间,则 $\min(S) = f(s, S)$。

$$
f(i, S) =
\begin{cases}
0 &(i \in S) \\
\frac{\sum_{i \to j} f(j, S)}{d_i} + 1 &(i \notin S)
\end{cases}
$$

可通过高斯消元求出,但复杂度过大不能接受。
考虑把原式化为 $f(i) = k_i \times f(father_i) + b_i$ 的形式,推导过程略。
对于每个查询状压处理 $\max(S)$ 不现实,需要处理出子集卷积即可 AC 。

同理可 Min-Max 容斥:

$$
\min(S) = \frac{1}{1 - \sum\limits_{S’ \subseteq S} \sum\limits_{u \in S’} p_u}
$$

FWT 一波即可。

HDU4336 - Card Collector

考虑 Min-Max 容斥。用 $\min(S)$ 表示 $S$ 中出现至少一个元素的期望时间,用 $\max(S)$ 表示 $S$ 中每一个元素都出现的期望时间。

则:

$$
\begin{aligned}
\min(S) &= \frac{1}{\sum\limits_{i \in S} p_i} \\
\max(S) &= \sum\limits_{S’ \subseteq S} \min(S’) (-1)^{|S’| - 1}
\end{aligned}
$$

答案显然是让我们求 $\max(\texttt{全集})$ ,故状压一下即可。

Min-Max 容斥学习笔记

感谢 lyc 哥哥上次给我讲了一下…然而我并没有听懂,只能自己再去学了一遍

Min-Max 容斥:

$$
\max(S) = \sum\limits_{S’ \subseteq S} \min(S’) (-1)^{|S’| - 1}
$$

可以用二项式反演证明:构造容斥函数 $f(x)$ 使得

$$
\max(S) = \sum\limits_{S’ \subseteq S} \min(S’) f(|S’|)
$$

考虑每个 $S’ \subseteq S$ 中 $\min(S’) = a_{x+1}$ 对答案的贡献为:

$$
g(x) = [x = 0] = \sum\limits_{i=0}^x {x \choose i} f(i+1)
$$

二项式反演得:

$$
\begin{aligned}
f(x + 1) &= \sum\limits_{i=0}^x (-1)^{x-i} {x \choose i} g(i) \\
\Rightarrow \ \ \ f(x + 1) &= (-1)^{x} \\
\Rightarrow \ \ \ f(x) &= (-1)^{x-1}
\end{aligned}
$$

所以:

$$
\begin{aligned}
\max(S) &= \sum\limits_{S’ \subseteq S} \min(S’) f(|S’|) \\
&= \sum\limits_{S’ \subseteq S} \min(S’) (-1)^{|S’| - 1}
\end{aligned}
$$

非常妙的一道状压题。

考虑依次加入每一个点,状态之间的转移和对答案的贡献只与每个深度的节点个数,因此我们可以这样定义状态:把这棵树的节点按深度排序,显然相邻两个的深度最多相差一,如果差等于一,状压出的对应位就是 1 ,否则就是 0 。利用这个即可进行 $O(2^n \times n ^ 2)$ 的转移。

还有一种 $O(n ^ 3)$ 的天顶星写法,但是我暂时不会,只能等以后补锅。

洛谷5104 - 红包发红包

在 $[0,w]$ 中等概率取出的值的期望是 $\frac{1}{2} w$ ,简单观察可以发现,答案就是 $\frac{1}{2} ^ k$ ,快速幂一下就好了。

需要注意的是,根据欧拉定理,若 $p$ 是质数:
$$a^b \equiv a ^ {b \mod \varphi(p)} (\mod p)$$
所以这题如果你直接给 $k$ 模下 $p$ 就会挂啦 233.

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×