隨機大法好（2021 電資圈接力發文活動） | 競程

前言

本來想寫連通分量跟 tarjan 的介紹，但我發現可能會寫得又臭又長，加上我不會畫畫，於是就決定來介紹更酷的東西。

第一篇教學文 owo

廢話不多說，直接進入正文

先備知識 — 如何產生亂數

懶人包：已經會的話可以直接跳過這一部分。

Reference ⟩

G.T. Wang - C++11 內建亂數函式庫使用教學：隨機亂數產生器與機率分布

要有一個可以產生亂數的工具，首先必須備齊三大工具：

1. 亂數種子（Random Seed）

點我

亂數的生成幾乎都是用一些複雜的數學公式（偽隨機），而種子的功能就是做為這些公式的某些初始參數。

常用的種子是時間資訊，取用方法有 time(NULL) 或是 chrono::steady_clock::now().time_since_epoch().count()。

另外也可以用 std::random_device，這東西會抓系統的一些隨機資訊來產生亂數，詳細介紹可以看上面那篇參考資料。

2. 引擎（Generator）

點我

隨機算法的核心，把種子餵給他後，就可以幫你產生一連串的亂數。

個人最常用的是 std::mt19937，背後的演算法是梅森旋轉演算法。

宣告一個引擎的語法：引擎名稱(種子); 例如：std::mt19937 gen( time(NULL) );

其他引擎可以參考上面那篇文。

3. 數值分布（Distribution）

點我

分布的功能就是將引擎產生的數值，依照我們的需求轉換為各種機率分布，例如均勻分布、常態分布、二項分布等等。

基本上如果沒有特別的需求，使用 uniform distribution （均勻分布）就夠了。

如果是使用整數，語法是 std::uniform_int_distribution<int> 分布名稱(最小值, 最大值)。如果是使用小數，語法是 std::uniform_real_distribution<double> 分布名稱(最小值, 最大值)。

舉例：std::uniform_int_distribution<int> dis(0, 100); 而產生一個亂數的語法：分布(引擎)

其他數值分布可以參考上面的文章。

以下示範如何隨機產生 100 個介於 0~10000 的整數：

#include <chrono>
#include <random>
#include <iostream>

using namespace std;

int main() {
    mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
    uniform_int_distribution<int> dis(0, 10000);
    
    for (int i = 0; i < 100; i++) {
        cout << dis(gen) << endl;
    }
}

暖身：大數運算

題目來源：改編自 2020 資訊之芽團體賽

給一個正整數 $N$ ，令 $M = N \ \text{mod}\ 987654321$ ，請計算 $M^N \ \text{mod}\ 2$ 的結果。

$N \leq 10^{10^5}$ ，測試資料共 $\lfloor \pi \rfloor$ 筆。

完蛋，看起來好難喔，怎麼辦 QQ？

別忘了，解一道題目最重要的步驟便是好好觀察題目的性質。

注意到 $\lfloor \pi \rfloor = 3$ ，並且答案只有 $0$ 跟 $1$ 兩種。

因此我們可以不管 $N$ ，直接隨機決定要輸出 $0$ 還是 $1$ 就好。

這個做法的 AC 機率 $= (\frac{1}{2})^3 = \frac{1}{8}$ 。期望上只要丟 8 次就會過了，夠有緣的甚至一發爽爽 AC。

類題練習

延續例題，只是測試資料從 $\lfloor \pi \rfloor$ 筆變成 $\lfloor 🥧 \rfloor$ 筆。

提示一

🥧 = pie

提示二

pie = $\pi e$

作法

$\lfloor 🥧 \rfloor = 8$ ，和例題的作法一樣，有 $\frac{1}{256}$ 的機率可以 AC，期望只要丟 256 次就行了。

不那麼隨機的隨機

Note ⟩

先備知識：前綴和

先看簡單版的題目：

輸入一個長度為 $N$ 的陣列 $A$ ，接下來有 $Q$ 筆詢問。

第 $i$ 筆詢問有兩個數字 $L_i, R_i$ ，問每種數字在區間 $A[L_i] \sim A[R_i]$ 出現次數是否恰好為 $3$ 的倍數？

對於每筆詢問，輸出一行 YES 或 NO。

$N \leq 10^5, Q = 3,$ 測資只有一筆。

$1 \leq A_i \leq N$

觀察

首先先盯著這個問題，然後會發現一個關鍵的性質 — $Q = 3$ ，且答案只有兩種。類似剛才所學到的作法，枚舉這三筆詢問要輸出的是 YES 或 NO，期望只要丟 8 次就會過了嗯嗯嗯嗯。不要跟我說什麼 O(NQ) 暴力統計出現次數就可以解決我不聽我不聽我不聽

接著是加強版：

輸入一個長度為 $N$ 的陣列 $A$ ，接下來有 $Q$ 筆詢問。

第 $i$ 筆詢問有兩個數字 $L_i, R_i$ ，問每種數字在區間 $A[L_i] \sim A[R_i]$ 出現次數是否恰好為 $3$ 的倍數？

對於每筆詢問，輸出一行 YES 或 NO。

$N \leq 10^5, Q \leq 10^5$

$1 \leq A_i \leq N$

有個很聰明的作法，用文字不太好形容，直接舉例子。

假設陣列是 $[1, 2, 1, 1, 2, 1, 2, 2]$ 。

讓 $1$ 映射到任意數字 $x$ ， $2$ 映射到任意數字 $y$ 。

定義陣列 $B$ 如下：

陣列 $A$	1	2	1	1	2	1	2	2
陣列 $B$	$x$	$y$	$x$	$-2x$	$y$	$x$	$-2y$	$y$

概念就是，若數字為 $a$ ，其對應到的數字為 $m_a$ ，若該數字由左往右出現第「 $3$ 的倍數」次，則它在 $B$ 陣列中的值就要被設為 $-2 m_a$ ，反之則設為 $m_a$ 。

有了 $B$ 陣列，該如何判斷答案呢？

詢問的時候，若每種數字在區間 $[L_i, R_i]$ 出現次數皆為 3 的倍數，

則代表

$B[L_i] + B[L_i + 1] + ... + B[R_i] = 0$

這時就輸出 YES，否則輸出 NO。

而只要套用前綴和的技巧， $O(1)$ 回答 $B[L_i] + ... + B[R_i]$ ，就可在 $O(N + Q)$ 的時間內解決這題。

然而這作法還是有問題，因為 $B[L_i] + ... + B[R_i] = 0$ 的時候答案不一定是 YES。

舉例

陣列 $A$	1	1	1	2
陣列 $B$	$x$	$x$	$-2x$	$y$

讓 $x = 1, y = 2$ ，詢問 $[3, 4]$ 便會判斷錯誤。

問題在於 $A$ 中每個數字的映射範圍不能太小，否則很容易就會發生判斷錯誤的情況。

這時只要保證 $A$ 的每個數字隨機映射到的數字夠大、夠分散，例如隨機映射到 $[1, 10^9]$ 之間的數字，就有很高的機率能夠避開判斷失誤，穩穩 AC。

類題練習

題目：資芽 OJ 793 — 想不到題目標題QQ

我不會下標題，但這真的很有趣

Note ⟩

先備知識：二分搜

經典例題：資芽 OJ 794 — 區間絕對眾數

若某個數字 $x$ 在一個序列中出現次數 嚴格超過 序列長度的一半，稱 $x$ 為該序列的絕對眾數。

輸入一個長度為 $N$ 的正整數序列 $a_1, ..., a_N$ ，接下來有 $Q$ 筆詢問。

每筆詢問輸入 $l_i, r_i$ ，輸出區間 $[l_i, r_i]$ 的絕對眾數，若不存在請輸出 $0$ 。

$N, Q \leq 5 \times 10^5, 1 \leq a_i \leq 5 \times 10^5$

提示

如果我在一個區間隨機戳一個數字的話...

溫馨提示

建議直接點開以下提示，因為我本人想了一年多才在偶然獲得的提示下想到這題的關鍵。

對，整整一年。

破題關鍵

如果我在一個區間隨機戳一個數字的話，那我戳中絕對眾數的機率會是 $\frac{1}{2}$ 。

完整做法

那我們不妨在這個區間內隨機選 $30$ 個數字，然後一一檢查它們是不是絕對眾數，而連續 $30$ 次都戳不中絕對眾數的機率略小於 $10^{-9}$ ，基本上可以忽略這微小的機率，假裝一定會戳中。

因此單筆詢問的正確率為 $1 - 10^{-9}$ ，連續 $Q$ 筆詢問都正確的機率為 $(1 - 10^{-9})^Q$ ，若 $Q = 5 \times 10^5$ ，則 AC 的機率約為 $99.95\%$ ，幾乎可以一發 AC，一次不過第二次也會過。如果有人可以連續兩次都 WA 的，請截圖 + 傳 code 私訊我，請你吃三碗拉麵。

現在還有一個問題要解決：要怎麼快速知道一個數字在某個區間內是不是絕對眾數？或者，要怎麼快速知道一個數字在某個區間內出現幾次？

有個比較直覺的作法，先開一個大小 $5 \times 10^5$ 的 vector 陣列 $pos$ ， $pos[a]$ 存 $a$ 這個數字在原序列中依序出現的位置。

舉例如下：

$i$	1	2	3	4	5	6
$a_i$	1	2	1	1	2	2

則 pos 陣列如下：

$a$	$pos[a]$
1	1, 3, 4
2	2, 5, 6

要詢問一個數字 $a$ 的在區間 $[l, r]$ 的出現次數，可以換個角度，改成詢問 $pos[a]$ 中有幾個數字介於 $l \sim r$ 之間。

由於 $pos[a]$ 嚴格遞增，因此對 $pos[a]$ 做二分搜，搜尋 「第一個大於等於 $l$ 的數字」的位置，以及 「第一個大於 $r$ 的數字」的位置。兩個搜到的答案相減，就是 $a$ 在該區間出現的次數。

舉例如下：

沿用上例的 pos 陣列，假設詢問 1 在區間 $[2, 5]$ 出現幾次，

則可以反過來問 $pos[1]$ 中，有幾個數字介於 $2 \sim 5$ 之間。而符合條件的數字以紅色標示：

$a$	$pos[a]$
1	1, 3, 4
2	2, 5, 6

這件事情可以用二分搜做到。

懶的寫二分搜的話可以用 lower_bound 函式，我是怪人我每次二分搜都還是會自己刻。

這個做法的總複雜度為 $O(N + k \ Q \log N)$ ， $k$ 是每次詢問挑的數字個數（上面的作法 $k = 30$ ）。

如果會 TLE 的話可以把 $k$ 改小一點，會 WA 的話就改大一點。

另解

這題還有另外一個非隨機做法，不僅速度更快（經實測時間是隨機的一半），而且正確率 $100 \%$ ，有興趣的可以上網搜尋「戰鬥線段樹」，也是一個超酷的作法。

或是參考台中一中 x 資奧二階大佬 abc864197532 的文章： https://abc864197532.github.io/2021/02/07/tioj-2140/

前言

先備知識 — 如何產生亂數

暖身：大數運算

不那麼隨機的隨機

我不會下標題，但這真的很有趣

更多隨機