###### tags: `電資圈接力 Challenge`
<style>
.red {
color: #c2081a;
}
</style>
# 隨機大法好
----
## 前言
本來想寫連通分量跟 tarjan 的介紹，但我發現可能會寫得又臭又長，加上我不會畫畫，於是就決定來介紹更酷的東西。
第一篇教學文／
廢話不多說，直接進入正文
----
## 先備知識 — 如何產生亂數
**懶人包：已經會的話可以直接跳過這一部分。**
> 參考資料：https://blog.gtwang.org/programming/cpp-random-number-generator-and-probability-distribution-tutorial/
要有一個可以產生亂數的工具，首先必須備齊三大工具：
:::success
**1. 亂數種子（Random Seed）**
:::
:::spoiler 點我
亂數的生成幾乎都是用一些複雜的數學公式（偽隨機），而種子的功能就是做為這些公式的某些**初始參數**。
常用的種子是時間資訊，取用方法有 `time(NULL)` 或是 `chrono::steady_clock::now().time_since_epoch().count()`。
另外也可以用 `std::random_device`，這東西會抓系統的一些隨機資訊來產生亂數，詳細介紹可以看上面那篇參考資料。
:::
.
:::success
**2. 引擎（Generator）**
:::
:::spoiler 點我
隨機算法的核心，把種子餵給他後，就可以幫你產生一連串的亂數。
個人最常用的是 `std::mt19937`，背後的演算法是[梅森旋轉演算法](https://zh.wikipedia.org/wiki/%E6%A2%85%E6%A3%AE%E6%97%8B%E8%BD%AC%E7%AE%97%E6%B3%95)。
宣告一個引擎的語法：`引擎 名稱(種子);`
例如：`std::mt19937 gen( time(NULL) );`
其他引擎可以參考上面那篇文。
:::
.
:::success
**3. 數值分布（Distribution）**
:::
:::spoiler 點我
分布的功能就是將引擎產生的數值，依照我們的需求轉換為各種機率分布，例如均勻分布、常態分布、二項分布等等。
基本上如果沒有特別的需求，使用 `uniform distribution` （均勻分布）就夠了。
如果是使用整數，語法是 `std::uniform_int_distribution<int> 分布名稱(最小值, 最大值)`。
如果是使用小數，語法是 `std::uniform_real_distribution<double> 分布名稱(最小值, 最大值)`。
舉例：`std::uniform_int_distribution<int> dis(0, 100);`
而產生一個亂數的語法：`分布(引擎)`
其他數值分布可以參考上面的文章。
:::
.
:::spoiler 以下示範如何隨機產生 100 個介於 0~10000 的整數：
```cpp=
#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$ 筆。
> :::spoiler 提示一
> 🥧 = pie
> :::
> :::spoiler 提示二
> pie = $\pi e$
> :::
> :::spoiler 作法
> $\lfloor{\text{🥧}}\rfloor = 8$，和例題的作法一樣，有 $\frac{1}{256}$ 的機率可以 AC，期望只要丟 256 次就行了。
> :::
----
## 不那麼隨機的隨機
:::warning
**先備知識：前綴和**
:::
:::spoiler 先看簡單版的題目：
> 輸入一個長度為 $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 的倍數，
:::spoiler 則代表
$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。
> :::spoiler 舉例
> | 陣列$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](https://neoj.sprout.tw/problem/793/)
----
## 我不會下標題，但這真的很有趣
:::warning
**先備知識：二分搜**
:::
> **經典例題：[資芽 OJ 794 — 區間絕對眾數](https://neoj.sprout.tw/problem/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$
:::spoiler 提示
如果我在一個區間隨機戳一個數字的話...
:::
.
:::spoiler 溫馨提示
建議直接點開以下提示，因為我本人想了一年多才在偶然獲得的提示下想到這題的關鍵。
**對，整整一年。**
:::
.
:::spoiler 破題關鍵
如果我在一個區間隨機戳一個數字的話，那我戳中絕對眾數的機率會是 $\frac{1}{2}$。
:::
.
:::spoiler 完整做法
那我們不妨在這個區間內隨機選 $30$ 個數字，然後一一檢查它們是不是絕對眾數，而連續 $30$ 次都戳不中絕對眾數的機率略小於 $10^{-9}$，基本上可以忽略這微小的機率，假裝一定會戳中。
因此單筆詢問的正確率為 $1 - 10^{-9}$，連續 $Q$ 筆詢問都正確的機率為 $(1 - 10^{-9})^Q$，若 $Q = 5 \times 10^5$，則 AC 的機率約為 $99.95\%$，幾乎可以一發 AC，一次不過第二次也會過。**如果有人可以連續兩次都 WA 的，請截圖 + 傳 code 私訊我，請你吃三碗拉麵**。
::: info
現在還有一個問題要解決：要怎麼快速知道一個數字在某個區間內是不是絕對眾數？或者，要怎麼快速知道一個數字在某個區間內**出現幾次**？
有個比較直覺的作法，先開一個大小 $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, <span class="red">3, 4</span>** |
> | 2 | 2, 5, 6 |
>
> **這件事情可以用二分搜做到。**
>
> **懶的寫二分搜的話可以用 lower_bound 函式，我是怪人我每次二分搜都還是會自己刻。**
:::
.
這個做法的總複雜度為 $O(N + k \ Q \log N)$，$k$ 是每次詢問挑的數字個數（上面的作法 $k = 30$）。
如果會 TLE 的話可以把 $k$ 改小一點，會 WA 的話就改大一點。
.
:::spoiler 另解
這題還有另外一個非隨機做法，不僅速度更快（經實測時間是隨機的一半），而且正確率 $100 \%$，有興趣的可以上網搜尋「**戰鬥線段樹**」，也是一個超酷的作法。
或是參考台中一中 x 資奧二階大佬 **abc864197532** 的文章：
https://abc864197532.github.io/2021/02/07/tioj-2140/
:::
## 更多隨機
隨機有趣的題目遠不止這些，甚至經典分治題 —最近點對— 也有隨機演算法。
:::spoiler 想要更多有趣的題目請點我
:::spoiler 真的想要更多有趣的題目請再次點我
:::spoiler 真的真的想要解鎖更多有趣的題目拜託再次點我
使用電資圈接力的 tag 以解鎖更多
Sign in with Wallet
Connect another wallet