From af887b4b85a336555090e12f10b539658909a8cd Mon Sep 17 00:00:00 2001 From: mgt Date: Thu, 19 Nov 2020 19:15:29 +0800 Subject: [PATCH] Update docs/misc/rand-technique.md --- docs/misc/rand-technique.md | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/docs/misc/rand-technique.md b/docs/misc/rand-technique.md index d0e4c395..16f54600 100644 --- a/docs/misc/rand-technique.md +++ b/docs/misc/rand-technique.md @@ -134,7 +134,7 @@ author: Ir1d, partychicken, ouuan, Marcythm, TianyiQ - 理由: $\dfrac {(n-1)(m-1)}{nm}\cdot\dfrac{(n-2)(m-2)}{(n-1)(m-1)}\cdots\dfrac{(n-k)(m-k)}{(n-k+1)(m-k+1)}=\dfrac{(n-k)(m-k)}{nm}\geq \dfrac 14$ -而连续选完 $k$ 对 $(s,t)$ 后判断它们是否全部满足目标 I 很简单,只要再跑一遍强连通缩点,判断一下 $n,m$ 是否都减小了 $k$ 即可。注意到若每次减少 $k=\dfrac{\min(n,m)}2$ ,则 $min(n,m)$ 必在 $O(\log(n+m))$ 轮内变成 1,也就转化到了平凡的情况。 +而连续选完 $k$ 对 $(s,t)$ 后判断它们是否全部满足目标 I 很简单,只要再跑一遍强连通缩点,判断一下 $n,m$ 是否都减小了 $k$ 即可。注意到若每次减少 $k=\dfrac{\min(n,m)}2$ ,则 $\min(n,m)$ 必在 $O(\log(n+m))$ 轮内变成 1,也就转化到了平凡的情况。 ???+ note "算法伪代码" ```text -- 2.11.0