考虑 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 。

考虑到原问题等价于以下行列式的值:

$$
第 i 行的 l_i 到 r_i 的值为 1 ,其他为 0 。
$$

我们采用高斯消元,复杂度 $O(n ^ 3)$ ,可以获得 70 pts.

考虑优化,由于 $1$ 的位置是连续的区间,采用左偏树维护每个左端点的右端点最小值即可。

注意行列式中交换两列,行列式的值取相反数;如果不能消成单位矩阵,则行列式的值为 $0$ 。

高斯消元学习笔记

最近的模拟赛出现了一道坑爹的数学题,正解是上一篇博文所讲的数学插值。然而高斯消元还是可以拿到 65 分的成绩,没办法,凭借着我对其原理的依稀记忆我只能考场上手推高斯消元。

原理

高斯消元其实是个很简单的东西,无非就小学奥数的难度罢了。按照小学奥数的加减消元和代入消元即可完成。模板题给了你 n 个的 n 元一次多项式求解。我们可以通过加减消元合并为 n - 1 个 n - 1 元的一次多项式(合并相邻两个);于是,经过 n - 1 次合并我们就可以得到一个一元一次方程,可以很方便的得到解。我们再将解回代,即可解出方程。

Your browser is out-of-date!

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

×