隨機化技巧

概述

前置知識：隨機函數 和 概率初步

本文將對 OI/ICPC 中的隨機化相關技巧做一個簡單的分類，並對每個分類予以介紹。本文也將介紹一些在 OI/ICPC 中很少使用，但與 OI/ICPC 在風格等方面較為貼近的方法，這些內容前將用 (*) 標註。

這一分類並不代表廣泛共識，也必定不能囊括所有可能性，因此僅供參考。

記號和約定：

• \(\mathrm{Pr}[A]\) 表示事件 \(A\) 發生的概率。
• \(\mathrm{E}[X]\) 表示隨機變量 \(X\) 的期望。
• 賦值號 \(:=\) 表示引入新的量，例如 \(Y:=1926\) 表示引入值為 \(1926\) 的量 \(Y\)。

用隨機集合覆蓋目標元素

龐大的解空間中有一個（或多個）解是我們想要的。我們可以嘗試進行多次撒網，只要有一次能夠網住目標解就能成功。

例：三部圖的判定

問題

給定一張 \(n\) 個結點、\(m\) 條邊的簡單無向圖，用 RGB 三種顏色給每個結點染色 滿足任意一對鄰居都不同色，或者報告無解。

對每個點 \(v\)，從 \(\{R,G,B\}\) 中等概率獨立隨機地選一種顏色 \(C_v\)，並欽定 \(v\) 不 被染成 \(C_v\)。最優解恰好符合這些限制的概率，顯然是 \(\big(\frac 23\big)^n\)。

在這些限制下，對於一對鄰居 \((u,v)\)，「\(u,v\) 不同色」的要求等價於以下這條「推出」關係：

• 對於所有異於 \(C_u,C_v\) 的顏色 \(X\)，若 \(u\) 被染成 \(X\)，則 \(v\) 被染成 \(\{R,G,B\}\setminus\{X,C_v\}\)。

於是我們可以對每個 \(v\) 設置布爾變量 \(B_v\)，其取值表示 \(v\) 被染成兩種剩餘的顏色中的哪一種。藉助 2-SAT 模型即可以 \(O(n+m)\) 的複雜度解決這個問題。

這樣做，單次的正確率是 \(\big(\frac 23\big)^n\)。將算法重複運行 \(-\big(\frac 32\big)^n\log \epsilon\) 次，只要有一次得到解就輸出，這樣即可保證 \(1-\epsilon\) 的正確率。（詳見後文中「概率上界的分析」）

---

回顧：本題中「解空間」就是集合 \(\{R,G,B\}^n\)，我們每次通過隨機施加限制來在一個縮小的範圍內搜尋「目標解」——即合法的染色方案。

例：CodeChef SELEDGE

簡要題意

給定一張點、邊都有非負權值的無向圖，找到一個大小 \(\leq K\) 的邊集合 \(S\)，以最大化與 \(S\) 相連的點的權值和減去 \(S\) 的邊權和。一個點的權值只被計算一次。

觀察：如果選出的邊中有三條邊構成一條鏈，則刪掉中間的那條一定不劣；如果選出的邊中有若干條構成環，則刪掉任何一條一定不劣。

推論：最優解選出的邊集，一定構成若干個不相交的菊花圖（即直徑不超過 2 的樹）。

推論：最優解選出的邊集，一定構成一張二分圖。

我們對每個點等概率獨立隨機地染上黑白兩種顏色之一，並要求這一染色方案，恰好也是最優解所對應的二分圖的黑白染色方案。

嘗試計算最優解符合這一要求的概率：

• 考慮一張 \(n\) 個點的菊花圖，顯然它有 2 種染色方案，所以它被染對顏色的概率是 \(\dfrac 2{2^n}=2^{1-n}\)。
• 假設最優解中每個菊花的結點數分別為 \(a_1,\cdots,a_l\)，則一定有 \((a_1-1)+\cdots+(a_l-1)\leq K\)，其中 \(K\) 表示最多能夠選出的邊數。
• 從而所有菊花都被染對顏色的概率是 \(2^{1-a_1}\cdots 2^{1-a_l}\geq 2^{-K}\)。

在上述要求下，嘗試建立費用流模型計算最優答案：

• 建立二分圖，白點在左側並與 \(S\) 相連，黑點在右側並與 \(T\) 相連。
  • 對於白點 \(v\)，從 \(S\) 向它連一條容量為 1、費用為 \(-A_v\) 的邊，和一條容量為 \(\infty\)、費用為 0 的邊。
  • 對於黑點 \(v\)，從它向 \(T\) 連一條容量為 1、費用為 \(-A_v\) 的邊，和一條容量為 \(\infty\)、費用為 0 的邊。
• 對於原圖中的邊 \((u,v,B)\) 滿足 \(u\) 為白色、\(v\) 為黑色，連一條從 \(u\) 到 \(v\) 的邊，容量為 1，費用為 \(B\)。
• 在該圖中限制流量不超過 \(K\)，則最小費用的相反數就是答案。

用 SPFA 費用流求解的話，複雜度是 \(O\big(K^2(n+m)\big)\)，證明：

• 首先，顯然 SPFA 的運行次數 \(\leq K\)。
• 然後，在一次 SPFA 中，任何一個結點至多入隊 \(O(K)\) 次。這是因為：
  • 任意時刻有流量的邊不會超過 \(3K\) 條，否則就意味着在原圖中選了超過 \(K\) 條邊。
  • 對於任何一條長為 \(L\) 的增廣路，其中至少有 \(\dfrac L2-2\) 條邊是某條有流量的邊的反向邊，因為正向邊都是從圖的左側指向右側，只有這些反向邊才會從右側指向左側。
  • 綜合以上兩條，得到任意一條增廣路的長度不超過 \(6K+4\)。
• 綜上，複雜度是 \(O\big(K^2(n+m)\big)\)。

和上一題類似，我們需要把整個過程重複 \(-2^K \log\epsilon\) 次以得到 \(1-\epsilon\) 的正確率。總複雜度 \(O\big(2^KK^2(n+m)\cdot -\log\epsilon\big)\)。

用隨機元素命中目標集合

我們需要確定一個集合中的任意一個元素，為此我們隨機選取元素，以期能夠恰好命中這一集合。

例：Gym 101550I

簡要題意

有一張圖形如：兩條平行的鏈，加上連接兩鏈的兩條平行邊。給定這張圖上的若干條簡單路徑（每條路徑表示一次通話），請你選擇儘量少的邊放置竊聽器，以使得每條給定的路徑上都有至少一個竊聽器。

整張圖可以拆分為一個環加上四條從環伸出去的鏈。對於這四條鏈中的任何一條（記作 \(C\)），考慮在這條鏈上如何放置竊聽器，容易通過貪心算法得到滿足以下條件的方案：

• 在攔截所有 \(C\) 內部進行的通話的前提下，用的竊聽器數量最少。
• 在上一條的前提下，使得 \(C\) 上的竊聽器離環的最短距離儘可能小。
  • 作這一要求的目的是儘可能地攔截恰有一個端點在 \(C\) 內部的通話。

接着考慮鏈與環相接處的共計 4 條邊，我們暴力枚舉這些邊上有沒有放竊聽器。顯然，如果想要攔截跨越鏈和環的通話，在這 4 條邊上放竊聽器一定是最優的。現在，我們可以把通話線路分為以下幾種：

1. 完全在鏈上的通話線路。這些線路一定已經被攔截，故可以忽略。
2. 跨越鏈和環，且已經被攔截的通話線路。它們可以忽略。
3. 跨越鏈和環，且未被攔截的通話線路。我們可以直接截掉它在鏈上的部分（因為鏈上的竊聽器放置方案已經固定了），只保留環上的部分。
4. 完全在環上的通話線路。

至此，問題轉化成了環上的問題。

設最優解中在環上的邊集 \(S\) 上放置了竊聽器，如果我們已經確定了 \(S\) 中的任何一個元素 \(e\)，就可以：

• 先在 \(e\) 處斷環為鏈。
• 然後從 \(e\) 開始貪心，不斷找到下一個放置竊聽器的邊。注意到如果經過合適的預處理，貪心的每一步可以做到 \(O(1)\) 的複雜度。
• 從而以 \(O(|S|)\) 的複雜度解決問題。

我們考慮隨機選取環上的一條邊 \(e'\)，並欽定 \(e'\in S\) 再執行上述過程，重複多次取最優。

分析單次複雜度：

• 觀察：記 \(S'\) 表示所有選取了 \(e'\) 的方案中的最優解，則 \(|S'|\leq |S|+1\)。
• 從而單次複雜度 \(O(|S'|)=O(|S|)\)。

分析正確率：

• 顯然單次正確率 \(\dfrac {|S|}n\)，其中 \(n\) 表示環長。
• 所以需要重複 \(-\dfrac n{|S|}\log\epsilon\) 次以得到 \(1-\epsilon\) 的正確率。

綜上，該算法的複雜度 \(O\big(|S|\cdot -\dfrac n{|S|}\log\epsilon\big)=O(-n\log\epsilon)\)。

例：CSES 1685 New Flight Routes

簡要題意

給定一張有向圖，請你加最少的邊使得該圖強連通，需 輸出方案。

先對原圖進行強連通縮點。我們的目標顯然是使每個匯點能到達每個源點。

不難證明，我們一定只會從匯點到源點連邊，因為任何其他的連邊，都能對應上一條不弱於它的、從匯點到源點的連邊。

我們的一個核心操作是，取匯點 \(t\) 和源點 \(s\)（它們不必在同一個弱連通分量裏），連邊 \(t\to s\) 以 使得 \(s\) 和 \(t\) 都不再是匯點或源點（記作目標 I）。理想情況下這種操作每次能減少一個匯點和一個源點，那我們不斷操作直到只剩一個匯點或只剩一個源點，而這樣的情形就很平凡了。由此，我們猜測答案是源點個數與匯點個數的較大值。

不難發現，上述操作能夠達到目標 I 的充要條件是：\(t\) 擁有 \(s\) 以外的前驅、且 \(s\) 擁有 \(t\) 以外的後繼。可以證明（等會會給出證明），對於任意一張有着至少兩個源點和至少兩個匯點的 DAG，都存在這樣的 \((s,t)\)；但存在性的結論無法幫助我們構造方案，還需做其他分析。

• 有了這個充要條件還難以直接得到算法，主要的原因是連邊 \(t\to s\) 後可能影響其他 \((s',t')\) 二元組的合法性，這個比較難處理。

注意到我們關於源匯點間的關係知之甚少（甚至連快速查詢一對 \(s-t\) 間是否可達都需要 dfs + bitset 預處理，而時限並不允許這麼做），這提示我們需要某種非常一般和強大的性質。

觀察：不滿足目標 I 的 \((s,t)\) 至多有 \(n+m-1\) 對，其中 \(n\) 表示源點個數，\(m\) 表示匯點個數。

• 理由：對於每一對這樣的 \((s,t)\)，若把它看成 \(s,t\) 間的一條邊，則所有這些邊構成的圖形如若干條不相交的鏈，於是邊數不超過點數減一。
• 作出這一觀察的動機是，要想將存在性結論應用於算法，前置步驟往往是把定性的結果加強為定量的結果。

推論：等概率隨機選取 \((s,t)\)，滿足前述要求的概率 \(\geq \dfrac {(n-1)(m-1)}{nm}\)。

• 注意到這個結論嚴格強於先前給出的存在性結論。

推論：等概率獨立隨機地連續選取 \(\dfrac {\min(n,m)}2\) 對不含公共元素的 \((s,t)\)，並對它們 依次 操作（即連邊 \(t\to s\)），則這些操作全部滿足目標 I 的概率 \(\geq \dfrac 14\)。

• 理由：

\[ \begin{aligned} &\phantom{=\ }\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 \end{aligned} \]

而連續選完 \(k\) 對 \((s,t)\) 後判斷它們是否全部滿足目標 I 很簡單，只要再跑一遍強連通縮點，判斷一下 \(n,m\) 是否都減小了 \(k\) 即可。注意到若每次減少 \(k=\dfrac{\min(n,m)}2\)，則 \(\min(n,m)\) 必在 \(O\big(\log(n+m)\big)\) 輪內變成 1，也就轉化到了平凡的情況。

算法偽代碼

while(n>1 and m>1):
    randomly choose k=min(n,m)/2 pairs (s,t)
    add edge t->s for all these pairs
    if new_n>n-k or new_m>m-k:
        roll_back()
solve_trivial()

複雜度 \(O\big((|V|+|E|) \log |V|\big)\)。

---

回顧：我們需要確定任意一對能夠實現目標 I 的二元組 \((s,t)\)，為此我們隨機選擇 \((s,t)\)。

用隨機化獲得隨機數據的性質

如果一道題的數據隨機生成，我們可能可以利用隨機數據的性質解決它。而在有些情況下，即使數據並非隨機生成，我們也可以通過隨機化來給其賦予隨機數據的某些特性，從而幫助解決問題。

例：隨機增量法

隨機生成的元素序列可能具有「前綴最優解變化次數期望下很小」等性質，而隨機增量法就通過隨機打亂輸入的序列來獲得這些性質。

詳見 隨機增量法。

例：TopCoder MagicMolecule 隨機化解法

簡要題意

給定一張 \(n\) 個點、帶點權的無向圖，在其中所有大小不小於 \(\dfrac {2n}3\) 的團中，找到點權和最大的那個。

\(n\leq 50\)

不難想到折半搜索。把點集均勻分成左右兩半 \(V_L,V_R\)（大小都為 \(\dfrac n2\)），計算數組 \(f_{L,k}\) 表示點集 \(L\subseteq V_L\) 中的所有 \(\geq k\) 元團的最大權值和。接着我們枚舉右半邊的每個團 \(C_R\)，算出左半邊有哪些點與 \(C_R\) 中的所有點相連（這個點集記作 \(N_L\)），並用 \(f_{N_L,\frac 23 n-|C_R|}+\textit{value}(C_R)\) 更新答案。

• 注意到可以 \(O(1)\) 轉移每一個 \(f_{L,k}\)。具體地説，取 \(d\) 為 \(L\) 中的任意一個元素，然後分類討論：
  • 假設最優解中 \(d\) 不在團中，則從 \(f_{L\setminus \{d\},k}\) 轉移而來。
  • 假設最優解中 \(d\) 在團中，則從 \(f_{L\cap N(d),k}+\textit{value}(d)\) 轉移而來，其中 \(N(d)\) 表示 \(d\) 的鄰居集合。
  • 別忘了還要用 \(f_{L,k+1}\) 來更新 \(f_{L,k}\)。

這個解法會超時。嘗試優化：

• 平分點集時均勻隨機地劃分。這樣的話，最優解的點集 \(C_{res}\) 以可觀的概率也被恰好平分（即 \(|C_{res}\cap V_L|=|C_{res}\cap V_R|\)）。
  • 當然，\(|C_{res}|\) 可能是奇數。簡單起見，這裏假設它是偶數；奇數的情況對解法沒有本質改變。
  • 實驗發現，隨機嘗試約 20 次就能以很大概率有至少一次滿足該性質。也就是説，如果我們的算法依賴於「\(C_{res}\) 被平分」這一性質，則將算法重複執行 20 次取最優，同樣也能保證以很大概率得到正確答案。
• 有了這一性質，我們就可以直接欽定左側團 \(L\)、右側團 \(C_R\) 的大小都 \(\geq \dfrac n3\)。這會對複雜度帶來兩處改進：
  • \(f\) 可以省掉記錄大小的維度。
  • 因為只需考慮大小 \(\geq \dfrac n3\) 的團，所以需要考慮的左側團 \(L\) 和 右側團 \(C_R\) 的數量也大大減少至約 \(1.8\cdot 10^6\)。
• 現在的瓶頸變成了求單側的某一子集的權值和，因為這需要 \(O\big(2^{|V_L|}+2^{|V_R|}\big)\) 的預處理。
  • 解決方案：在 \(V_L,V_R\) 內部再次折半；當查詢一個子集的權值和時，將這個子集分成左右兩半查詢，再把答案相加。
• 這樣即可通過本題。

---

回顧：一個隨機的集合有着「在劃分出的兩半的數量差距不會太懸殊」這一性質，而我們通過隨機劃分獲取了這個性質。

隨機化用於哈希

例：UOJ #207 共價大爺遊長沙

簡要題意

維護一棵動態變化的樹，和一個動態變化的結點二元組集合。你需要支持：

• 刪邊、加邊。保證得到的還是一棵樹。
• 加入/刪除某個結點二元組。
• 給定一條邊 \(e\)，判斷是否對於集合中的每個結點二元組 \((s,t)\)，\(e\) 都在 \(s,t\) 間的簡單路徑上。

對圖中的每條邊 \(e\)，我們定義集合 \(S_e\) 表示經過該邊的關鍵路徑（即題中的 \((a,b)\)）集合。考慮對每條邊動態維護集合 \(S_e\) 的哈希值，這樣就能輕鬆判定 \(S_e\) 是否等於全集（即 \(e\) 是否是「必經之路」）。

哈希的方式是，對每個 \((a,b)\) 賦予 \(2^{64}\) 以內的隨機非負整數 \(H_{(a,b)}\)，然後一個集合的哈希值就是其中元素的 \(H\) 值的異或和。

這樣的話，任何一個固定的集合的哈希值一定服從 \(R:=\left\{0,1,\cdots,2^{64}-1\right\}\) 上的均勻分佈（換句話説，哈希值的取值範圍為 \(R\)，且取每一個值的概率相等）。這是因為：

1. 單個 \(H_{(a,b)}\) 顯然服從均勻分佈。
2. 兩個獨立且服從 \(R\) 上的均勻分佈的隨機變量的異或和，一定也服從 \(R\) 上的均勻分佈。自證不難。

從而該算法的正確率是有保障的。

至於如何維護這個哈希值，使用 LCT 即可。

例：CodeChef PANIC 及其錯誤率分析

本題的大致解法：

1. 可以證明¹ \(S(N)\) 服從一個關於 \(N\) 的 \(O(K)\) 階線性遞推式。
2. 用 BM 算法求出該遞推式。
3. 藉助遞推式，用凱萊哈密頓定理計算出 \(S(N)\)。

這裏僅關注第二部分，即如何求一個矩陣序列的遞推式。所以我們只需考慮下述問題：

問題

給定一個矩陣序列，該序列在模 \(P:=998244353\) 意義下服從一個齊次線性遞推式（遞推式中的數乘和加法運算定義為矩陣的數乘和加法），求出最短遞推式。

如果一系列矩陣服從一個遞推式 \(F\)，那麼它的每一位也一定服從 \(F\)。然而，如果對某一位求出最短遞推式 \(F'\)，則 \(F'\) 可能會比 \(F\) 更短，從而產生問題。

解決方案：給矩陣的每一位 \((i,j)\) 賦予一個 \(<P\) 的隨機權值 \(x_{i,j}\)，然後對於序列中每個矩陣計算其所有位的加權和模 \(P\) 的結果，再把每個矩陣算出的這個數連成一個數列，最後我們對所得數列運行 BM 算法。

錯誤率分析：

• 假設上述做法求得了不同於 \(F\)（且顯然也不長於 \(F\)）的 \(l\) 階遞推式 \(F'\)。
• 因為矩陣序列不服從 \(F'\)，所以一定存在矩陣中的某個位置 \((i,j)\)，滿足該位置對應的數列 \(S_{i,j}\) 在某個 \(N\) 處不服從 \(F'\)。也就是説：

\[ S(N)_{i,j}-F'_1S(N-1)_{i,j}-\cdots-F'_lS(N-l)_{i,j}\not\equiv 0\pmod {P} \]

• 假設 \((i,j)\) 是唯一的不服從的位置，則一定有：

\[ T_{i,j}:=\Big(x_{i,j}\cdot\big(S(N)_{i,j}-F'_1S(N-1)_{i,j}-\cdots-F'_lS(N-l)_{i,j}\big)\bmod P\Big)=0 \]

• 顯然這僅當 \(x_{i,j}=0\) 時才成立，概率 \(P^{-1}\)。
• 如果有多個不服從的位置呢？
  • 對每個這樣的位置 \((i,j)\)，易證 \(T_{i,j}\) 服從 \(R:=\{0,1,\cdots,P-1\}\) 上的均勻分佈。
  • 若干個互相獨立的、服從 \(R\) 上的均勻分佈的隨機變量，它們在模意義下的和，依然服從 \(R\) 上的均勻分佈。自證不難。
  • 從而這種情況下的錯誤率也是 \(P^{-1}\)。

例：UOJ #552 同構判定鴨 及其錯誤率分析

簡要題意

給定兩張邊權為小寫字母的有向圖 \(G_0,G_1\)，你要對這兩張圖分別算出「所有路徑對應的字符串構成的多重集」（可能是無窮集），並判斷這兩個多重集是否相等。如果不相等，你要給出一個最短的串，滿足它在兩個多重集中的出現次數不相等。

令 \(f_{K,i,j}\) 表示圖 \(G_K\) 中從點 \(i\) 開始的所有長為 \(j\) 的路徑，這些路徑對應的所有字符串構成的多重集的哈希值。按照 \(j\) 升序考慮每個狀態，轉移時枚舉 \(i\) 的出邊並欽定該邊為路徑上的第一條邊。

要判斷是否存在長度 \(=L\) 的壞串，只需把 \(\{f_{0,*,L}\}\) 和 \(\{f_{1,*,L}\}\) 各自「整合」起來再比較即可（通配符 * 這裏表示每一個結點，例如 \(\{f_{0,*,L}\}\) 表示全體 \(f_{0,i,L}\) 構成的集合，其中 \(i\) 取遍所有結點）。官方題解²中證明了最短壞串（如果存在的話）長度一定不超過 \(n_1+n_2\)，所以這個解法的複雜度是可靠的。

接下來考慮具體的哈希方式。注意到常規的哈希方法——即把串 \(a_1a_2\cdots a_k\) 映射到 \(\big(a_1+Pa_2+P^2a_3+\cdots+P^{k-1}a_k\big)\bmod Q\) 上、再把多重集的哈希值定為其中元素的哈希值之和模 \(Q\)——在這裏是行不通的。一個反例是，集合 {"ab","cd"} 與集合 {"cb","ad"} 的哈希值是一樣的，不論 \(P,Q\) 如何取值。

上述做法的問題在於，一個串的哈希值是一個和式，從而其中的每一項可以拆出來並重組。為避免這一問題，我們考慮把哈希值改為一個連乘式。此外，乘法交換律會使得不同的位不可區分，為避免這一點我們要為不同的位賦予不同的權值。

對每一個二元組 \((c,j)\)（其中 \(c\) 為字符，\(j\) 為整數表示 \(c\) 在某個串中的第幾位）我們都預先生成一個隨機數 \(x_{c,j}\)。然後我們把串 \(a_1a_2\cdots a_k\) 映射到 \(x_{a_1,1}x_{a_2,2}\cdots x_{a_k,k}\bmod Q\) 上（其中 \(Q\) 為 隨機選取 的質數）、再把多重集的哈希值定為其中元素的哈希值之和模 \(Q\)。接下來分析它的錯誤率。

(*)Schwartz–Zippel 引理

令 \(f\in F[z_1,\cdots,z_k]\) 為域 \(F\) 上的 \(k\) 元 \(d\) 次非零多項式，令 \(S\) 為 \(F\) 的有限子集，則至多有 \(d\cdot |S|^{k-1}\) 組 \((z_1,\cdots,z_k)\in S^k\) 滿足 \(f(z_1,\cdots,z_k)=0\)。

如果你不知道域是什麼

你只需記得這兩樣東西都是域：

1. 模質數的剩餘系，以及其上的各種運算。
2. 實數集，以及其上的各種運算。

推論：若 \(z_1,\cdots,z_k\) 都在 \(S\) 中等概率獨立隨機選取，則 \(\mathrm{Pr}\big[f(z_1,\cdots,z_k)=0\big]\leq \dfrac d{|S|}\)。

記 \(F\) 為模 \(Q\) 的剩餘系所對應的域，則對於一個 \(L\leq n_1+n_2\)，\(\sum\limits_i f_{0,i,L}\) 和 \(\sum\limits_i f_{1,i,L}\) 就分別對應着一個 \(F\) 上關於變元集合 \(\{x_{*,*}\}\) 的 \(L\) 次多元多項式，不妨將這兩個多項式記為 \(P_0,P_1\)。

假如兩個不同的字符串多重集的哈希值相同，則有兩種可能：

1. \(P_0\equiv P_1\pmod {Q}\)，即 \(P_0,P_1\) 的每一項係數在模 \(Q\) 意義下都對應相等。
2. \(P_0\not\equiv P_1\pmod {Q}, P_0(x_{*,*})\equiv P_1(x_{*,*})\pmod {Q}\)，即 \(P_0,P_1\) 雖然不恆等，但我們選取的這一組 \(\{x_{*,*}\}\) 恰好使得它們在此處的點值相等。

分析前者發生的概率：

• 觀察：對於任意的 \(A\neq B; A,B\leq N\) 和隨機選取的質數 \(Q\leq Q_{\max}\)，一定有：

\[ \mathrm{Pr}\big[A\equiv B\pmod {Q}\big]=O\Big(\dfrac{\log N \log Q_{max}}{Q_{max}}\Big) \]

• 這是因為：使 \(A\equiv B\) 成立的 \(Q\) 一定滿足 \(Q\big|(A-B)\)，這樣的 \(Q\) 有 \(\omega(A-B)\leq \log_2 N\) 個；而由質數定理，\(Q_{\max}\) 以內不同的質數又有 \(\Theta\Big(\dfrac {Q_{\max}}{\log Q_{\max}}\Big)\) 個。將兩者相除即可得到上式。
• 在上述觀察中取 \(A,B\)（滿足 \(A\neq B\)）為某一特定項在 \(P_0,P_1\) 中的係數（也就等於該項對應的串在 \(G_0,G_1\) 中的出現次數），則易見 \(A,B\leq (m_1+m_2)^{L}\)，得到：

\[ \mathrm{Pr}\big[A\equiv B\pmod {Q}\big]=O\Big(\dfrac{L\log (m_1+m_2) \log Q_{max}}{Q_{max}}\Big) \]

• 所以取 \(Q_{\max}\approx 10^{12}\) 就綽綽有餘。如果機器無法支持這麼大的整數運算，可以用雙哈希代替。

分析後者發生的概率：

• 在 Schwartz–Zippel 引理中：
  • 取域 \(F\) 為模 \(Q\) 的剩餘系對應的域
  • 取 \(f(x_{*,*})=P_0(x_{*,*})-P_1(x_{*,*})\) 為 \(L\) 次非零多項式
  • 取 \(S=F\)
• 得到：所求概率 \(\leq \dfrac LQ\)。

注意到我們需要對每個 \(L\) 都能保證正確性，所以要想保證嚴謹的話還需用 Union Bound（見後文）説明一下。

實踐上我們不必隨機選取模數，因為——比如説——用自己的生日做模數的話，實際上已經相當於隨機數了。

例：（*）子矩陣不同元素個數

問題

給定 \(n\times m\) 的矩陣，\(q\) 次詢問一個連續子矩陣中不同元素的個數，要求在線算法。

允許 \(\epsilon\) 的相對誤差和 \(\delta\) 的錯誤率，換句話説，你要對至少 \((1-\delta)q\) 個詢問給出離正確答案相對誤差不超過 \(\epsilon\) 的回答。

\(n\cdot m\leq 2\cdot10^5;q\leq 10^6;\epsilon=0.5,\delta=0.2\)

引理：令 \(X_{1\cdots k}\) 為互相獨立的隨機變量，且取值在 \([0,1]\) 中均勻分佈，則 \(\mathrm{E}\big[\min\limits_i X_i\big]=\dfrac 1{k+1}\)。

• 證明：考慮一個單位圓，其上分佈着 相對位置 均勻隨機的 \(k+1\) 個點，分別在位置 \(0,X_1,X_2,\cdots,X_k\) 處。那麼 \(\min\limits_i X_i\) 就等於 \(k+1\) 段空隙中特定的一段的長度。而因為這些空隙之間是「對稱」的，所以其中任何一段特定空隙的期望長度都是 \(\dfrac 1{k+1}\)。

我們取 \(k\) 為不同元素的個數，並藉助上述引理來從 \(\min\limits_i X_i\) 反推得到 \(k\)。

考慮採用某個哈希函數，將矩陣中每個元素都均勻、獨立地隨機映射到 \([0,1]\) 中的實數上去，且相等的元素會映射到相等的實數。這樣的話，一個子矩陣中的所有元素對應的那些實數，在去重後就恰好是先前的集合 \(\{X_1,\cdots,X_k\}\) 的一個實例，其中 \(k\) 等於子矩陣中不同元素的個數。

於是我們得到了算法：

1. 給矩陣中元素賦 \([0,1]\) 中的哈希值。為保證隨機性，哈希函數可以直接用 map 和隨機數生成器實現，即每遇到一個新的未出現過的值就給它隨機一個哈希值。
2. 回答詢問時設法求出子矩陣中哈希值的最小值 \(M\)，並輸出 \(\dfrac 1M-1\)。

然而，這個算法並不能令人滿意。它的輸出值的期望是 \(\mathrm{E}\Big[\dfrac 1{\min\limits_i X_i}-1\Big]\)，但事實上這個值並不等於 \(\dfrac 1{\mathrm{E}\big[\min\limits_i X_i\big]}-1=k\)，而（可以證明）等於 \(\infty\)。

也就是説，我們不能直接把 \(\min\limits_i X_i\) 的單次取值放在分母上，而要先算得它的期望，再把期望值放在分母上。

怎麼算期望值？多次隨機取平均。

我們用 \(C\) 組不同的哈希函數分別執行前述過程，回答詢問時計算出 \(C\) 個不同的 \(M\) 值，並算出其平均數 \(\overline M\)，然後輸出 \(\big(\overline M\big)^{-1}-1\)。

實驗發現取 \(C\approx 80\) 即可滿足要求。嚴格證明十分繁瑣，在此略去。

最後，怎麼求子矩陣最小值？用二維 S-T 表即可，預處理 \(O(nm\log n\log m)\)，回答詢問 \(O(1)\)。

隨機化在算法中的其他應用

隨機化的其他作用還包括：

• 防止被造數據者用針對性數據卡掉。例如在搜索時隨機打亂鄰居的順序。
• 保證算法過程中進行的「操作」具有（某種意義上的）均勻性。例如 模擬退火 算法。

在這些場景下，隨機化常常（但並不總是）與亂搞、騙分等做法掛鈎。

例：「TJOI2015」線性代數

本題的標準算法是網絡流，但這裏我們採取這樣的亂搞做法：

• 每次隨機一個位置，把這個位置取反，判斷大小並更新答案。

代碼

#include <algorithm>
#include <cstdlib>
#include <iostream>

int n;

int a[510], b[510], c[510][510], d[510];
int p[510], q[510];

int maxans = 0;

void check() {
  memset(d, 0, sizeof d);
  int nowans = 0;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) d[i] += a[j] * c[i][j];
  for (int i = 1; i <= n; i++) nowans += (d[i] - b[i]) * a[i];
  maxans = std::max(maxans, nowans);
}

int main() {
  srand(19260817);
  std::cin >> n;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) std::cin >> c[i][j];
  for (int i = 1; i <= n; i++) std::cin >> b[i];
  for (int i = 1; i <= n; i++) a[i] = 1;
  check();
  for (int T = 1000; T; T--) {
    int tmp = rand() % n + 1;
    a[tmp] ^= 1;
    check();
  }
  std::cout << maxans << '\n';
}

例：（*）隨機堆³

可並堆最常用的寫法應該是左偏樹了，通過維護樹高讓樹左偏來保證合併的複雜度。然而維護樹高有點麻煩，我們希望儘量避開。

那麼可以考慮使用隨機堆，即不按照樹高來交換兒子，而是隨機交換。

代碼

struct Node {
  int child[2];
  long long val;
} nd[100010];

int root[100010];

int merge(int u, int v) {
  if (!(u && v)) return u | v;
  int x = rand() & 1, p = nd[u].val > nd[v].val ? u : v;
  nd[p].child[x] = merge(nd[p].child[x], u + v - p);
  return p;
}

void pop(int &now) { now = merge(nd[now].child[0], nd[now].child[1]); }

隨機堆對堆的形態沒有任何硬性或軟性的要求，合併操作的期望複雜度對任何兩個堆（作為 merge 函數的參數）都成立。下證。

期望複雜度的證明

將證，對於任意的堆 \(A\)，從根節點開始每次隨機選左或者右走下去（直到無路可走），路徑長度（即路徑上的結點數）的期望值 \(h(A)\leq\log_2 (|A|+1)\)。

• 注意到在前述過程中合併堆 \(A,B\) 的期望複雜度是 \(O\big(h(A)+h(B)\big)\) 的，所以上述結論可以保證隨機堆的期望複雜度。

證明採用數學歸納。邊界情況是 \(A\) 為空圖，此時顯然。下設 \(A\) 非空。

假設 \(A\) 的兩個子樹分別為 \(L,R\)，則：

\[ \begin{align} h(A) &=1+\frac{h(L)+h(R)}2 \\&\leq1+\frac{\log_2(|L|+1)+\log_2(|R|+1)}2 \\&=\log_2{2\sqrt{(|L|+1)(|R|+1)}} \\&\leq\log_2{\frac{2\big((|L|+1)+(|R|+1)\big)}2} \\&=\log_2{(|A|+1)} \end{align} \]

證畢。

與隨機性有關的證明技巧

以下列舉幾個比較有用的技巧。

自然，這寥寥幾項不可能就是全部；如果你瞭解某種沒有列出的技巧，那麼歡迎補充。

概率上界的分析

詳見 概率不等式 頁面。

除了上述頁面中提到的各種不等式外，推導過程中還經常會用到以下結論：

自然常數的使用：\(\Big(1-\dfrac{1}{n}\Big)^n\leq \dfrac{1}{\mathrm{e}},\forall n\geq1\)

• 左式關於 \(n\geq 1\) 單調遞增且在 \(+\infty\) 處的極限是 \(\dfrac{1}{\mathrm{e}}\)，因此有這個結論。
• 這告訴我們，如果 \(n\) 個互相獨立的事件，每個的發生概率為 \(1-\dfrac 1n\)，則它們全部發生的概率至多為 \(\dfrac{1}{\mathrm{e}}\)。

「耦合」思想

「耦合」思想常用於同時處理超過一個有隨機性的對象，或者同時處理隨機的對象和確定性的對象。

引子：隨機圖的連通性

問題

對於 \(n \in \mathbf{N}^*; p,q\in [0,1]\) 且 \(q\leq p\)，求證：隨機圖 \(G_1(n,p)\) 的連通分量個數的期望值不超過隨機圖 \(G_2(n,q)\) 的連通分量個數的期望值。這裏 \(G(n,\alpha)\) 表示一張 \(n\) 個結點的簡單無向圖 \(G\)，其中 \(\dfrac {n(n-1)}2\) 條可能的邊中的每一條都有 \(\alpha\) 的概率出現，且這些概率互相獨立。

這個結論看起來再自然不過，但嚴格證明卻並不那麼容易。

證明思路

我們假想這兩張圖分別使用了一個 01 隨機數生成器來獲知每條邊存在與否，其中 \(G_1\) 的生成器 \(T_1\) 每次以 \(p\) 的概率輸出 1，\(G_2\) 的生成器 \(T_2\) 每次以 \(q\) 的概率輸出 1。這樣，要構造一張圖，就只需把對應的生成器運行 \(\dfrac {n(n-1)}2\) 遍即可。

現在我們把兩個生成器合二為一。考慮隨機數生成器 \(T\)，每次以 \(q\) 的概率輸出 0，以 \(p-q\) 的概率輸出 1，以 \(1-p\) 的概率輸出 2。如果我們將這個 \(T\) 運行 \(\dfrac {n(n-1)}2\) 遍，就能同時構造出 \(G_1\) 和 \(G_2\)。具體地説，如果輸出是 0，則認為 \(G_1\) 和 \(G_2\) 中都沒有當前考慮的邊；如果輸出是 1，則認為只有 \(G_1\) 中有當前考慮的邊；如果輸出是 2，則認為 \(G_1\) 和 \(G_2\) 中都有當前考慮的邊。

容易驗證，這樣生成的 \(G_1\) 和 \(G_2\) 符合其定義，而且在每個實例中，\(G_2\) 的邊集都是 \(G_1\) 邊集的子集。因此在每個實例中，\(G_2\) 的連通分量個數都不小於 \(G_1\) 的連通分量個數；那麼期望值自然也滿足同樣的大小關係。

這一段證明中用到的思想被稱為「耦合」，可以從字面意思來理解這種思想。本例中它體現為把兩個本來獨立的隨機過程合二為一。

應用：NERC 2019 Problem G: Game Relics

簡要題意

有若干個物品，每個物品有一個價格 \(c_i\)。你想要獲得所有物品，為此你可以任意地進行兩種操作：

1. 選擇一個未擁有的物品 \(i\)，花 \(c_i\) 塊錢買下來。
2. 花 \(x\) 塊錢從所有物品（包括已經擁有的）中等概率隨機抽取一個。如果尚未擁有該物品，則直接獲得它；否則一無所獲，但是會返還 \(\dfrac x2\) 塊錢。\(x\) 為輸入的常數。

問最優策略下的期望花費。

觀察：如果選擇抽物品，就一定會一直抽直到獲得新物品為止。

• 理由：如果抽一次沒有獲得新物品，則新的局面和抽物品之前的局面一模一樣，所以如果舊局面的最優行動是「抽一發」，則新局面的最優行動一定也是「再抽一發」。

我們可以計算出 \(f_k\) 表示：如果當前已經擁有 \(k\) 個不同物品，則期望要花多少錢才能抽到新物品。根據剛才的觀察，我們可以直接把 \(f_k\) 當作一個固定的代價，即轉化為「每次花 \(f_k\) 塊錢隨機獲得一個新物品」。

期望代價的計算

顯然 \(f_k=\dfrac x2 \cdot (R-1)+x\)，其中 \(R\) 表示要得到新物品期望的抽取次數。

引理：如果一枚硬幣有 \(p\) 的概率擲出正面，則首次擲出正面所需的期望次數為 \(\dfrac 1p\)。

• 感性理解：\(\dfrac 1p \cdot p = 1\)，所以扔這麼多次期望得到 1 次正面，看起來就比較對。
• 這種感性理解可以通過 大數定律 嚴謹化，即考慮 \(n\to \infty\) 次「不斷拋硬幣直到得到正面」的實驗。推導細節略。
• 另一種可行的證法是，直接把期望的定義帶進去暴算。推導細節略。

顯然抽一次得到新物品的概率是 \(\dfrac {n-k}n\)，那麼 \(R=\dfrac n{n-k}\)。

結論：最優策略一定是先抽若干次，再買掉所有沒抽到的物品。

這個結論符合直覺，因為 \(f_k\) 是關於 \(k\) 遞增的，早抽似乎確實比晚抽看起來好一點。

證明

先考慮證明一個特殊情況。將證：

• 隨機過程 \(A\)：先買物品 \(x\)，然後不斷抽直到得到所有物品
• ……一定不優於……
• 隨機過程 \(B\)：不斷抽直到得到 \(x\) 以外的所有物品，然後如果還沒有 \(x\) 則買下來

考慮讓隨機過程 \(A\) 和隨機過程 \(B\) 使用同一個隨機數生成器。即，\(A\) 的第一次抽取和 \(B\) 的第一次抽取會抽到同一個元素，第二次、第三次……也是一樣。

顯然，此時 \(A\) 和 \(B\) 抽取的次數必定相等。對於一個被 \(A\) 抽到的物品 \(y\neq x\)，觀察到：

• \(A\) 中抽到 \(y\) 時已經持有的物品數，一定大於等於 \(B\) 中抽到 \(y\) 時已經持有的物品數。

因此 \(B\) 的單次抽取代價不高於 \(A\) 的單次抽取代價，進而抽取的總代價也不高於 \(A\)。

顯然 \(B\) 的購買代價同樣不高於 \(A\)。綜上，\(B\) 一定不劣於 \(A\)。

然後可以通過數學歸納把這一結論推廣到一般情況。具體地説，每次我們找到當前策略中的最後一次購買，然後根據上述結論，把這一次購買移到最後一定不劣。細節略。

基於這個結論，我們再次等價地轉化問題：把「選一個物品並支付對應價格購買」的操作，改成「隨機選一個未擁有的物品並支付對應價格購買」。等價性的理由是，既然購買只是用來掃尾的，那選到哪個都無所謂。

現在我們發現，「抽取」和「購買」，實質上已經變成了相同的操作，區別僅在於付出的價格不同。選擇購買還是抽取，對於獲得物品的順序毫無影響，而且每種獲得物品的順序都是等可能的。

觀察：在某一時刻，我們應當選擇買，當且僅當下一次抽取的代價（由已經抽到的物品數確定）大於剩餘物品的平均價格（等於的話則任意）。

• 可以證明，隨着時間的推移，抽取代價的增速一定不低於剩餘物品均價的增速。這説明從抽到買的「臨界點」只有一個，進一步驗證了先前結論。

最後，我們枚舉所有可能的局面（即已經擁有的元素集合），算出這種局面出現的概率（已有元素的排列方案數除以總方案數），乘上當前局面最優決策的代價（由擁有元素個數和剩餘物品總價確定），再加起來即可。這個過程可以用揹包式的 DP 優化，即可通過本題。

---

回顧：可以看到，耦合的技巧在本題中使用了兩次。第一次是在證明過程中，令兩個隨機過程使用同一個隨機源；第二次是把購買轉化成隨機購買（即引入隨機源），從而使得購買和抽取這兩種操作實質上「耦合」為同一種操作（即令抽取和購買操作共享一個隨機源）。

參考資料

---

1. PANIC - Editorial ↩

2. UOJ NOI Round #4 Day2 題解 ↩

3. Anna Gambin and Adam Malinowski, Randomized Meldable Priority Queues ↩

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Ir1d, partychicken, ouuan, Marcythm, TianyiQ
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用