Gino's Blog

從 Scratch 開始的資工之路

0%

電資圈接力文—隨機大法好

Posted on Edited on

前言

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

第一篇教學文 :D
廢話不多說，直接進入正文


先備知識 — 如何產生亂數

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

參考資料：https://blog.gtwang.org/programming/cpp-random-number-generator-and-probability-distribution-tutorial/

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

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 的整數： 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#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{\text{🥧}}\rfloor$ 筆。

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

不那麼隨機的隨機

先備知識：前綴和

先看簡單版的題目：

輸入一個長度為 $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


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

先備知識：二分搜

經典例題：資芽 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/