<style> .reveal .slides { text-align: left; font-size:28px; } </style> # random --- * 要怎麼random(產生亂數) * hash * 更多 random 題目 ---- ## 產生亂數 ---- ## 產生亂數 亂數？很簡單啊，大一程式設計就有教 ```cpp! rand(); srand(seed); ``` 但真的好嗎？ ---- 在某些系統上 rand() 回傳範圍為 [$[0, ?]$](https://cplusplus.com/reference/cstdlib/RAND_MAX/#:~:text=This%20value%20is-,library%2Ddependent,-%2C%20but%20is%20guaranteed) $?$為一個數值，根據library or 系統決定 解決方法： - rand()拼成很多次很大的數字 - 用 mt19937 :D 以下會用 mt19937 實作隨機 ---- 在數學意義上並沒有真正的亂數，因此都只能用時間種子或者是怪怪的公式去假裝亂數 所以我們今天使用的是時間種子 ```cpp chrono::steady_clock::now().time_since_epoch().count() ``` 那記得使用這個要引入標頭檔 ```cpp #include<chrono> ``` 這是一個單位以 ms 來計算的時間亂數 ---- 分析 ```cpp chrono::steady_clock::now().time_since_epoch().count() ``` 首先 $steady\_clock$ 是一個單調的時鐘 然後 $now()$ 就是指現在的時間 接著 $time\_since\_epoch()$ 是指 現在獲取的 $now$ 到時間元年的間隔 最後 $count()$ 當然就是指有幾個間隔 *時間元年 1970/01/01 ---- 再來是產生器，我們會使用到的是 mt19937 什麼是mt19937呢，背後支持的數學演算法是梅森旋轉算法，可以使得在一個範圍內有隨機分布。 那要怎麼產生呢? ```cpp mt19937 變數名稱(亂數種子); ``` 所以我們的定義就會變成 ```cpp mt19937 mt(chrono::steady_clock::now().time_since_epoch().count()); ``` ---- 那我們就可以開始利用mt了 那因為mt是我們的產生器，我們還需要給他一個分布的範圍 ```cpp uniform_int_distribution<> dis(0, 1e9); ``` 那他的預設值就是int 如果今天要用小數點的話就分別是以下 ```cpp uniform_int_distribution<int> 分布變數名稱(最小值, 最大值); uniform_real_distribution<double> 分布變數名稱(最小值, 最大值); ``` ---- 所以最後就會這樣寫出東西 ```cpp #include<iostream> #include<random> #include<chrono> using namespace std; void solve(){ mt19937 mt(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution<> dis(0, 1e9); cout<<dis(mt)<<endl; } int main(){ solve(); return 0; } ``` ---- ## Shuffle random標頭檔下有shuffle函式 ```cpp shuffle(arr,arr+n,mt);//開頭,結尾,亂數產生器 ``` 跟sort的用法一樣，直接把你的arr全部打亂。 --- ## 算數學時間 ---- ## 簡單的練習 題目有 $T$ 筆測資，每筆測資你的程式會有 $p$ 的機率答對，並且你做了 $k$ 次取最好的，請問你 AC 的機率是多少 ---- 題目有 $T$ 筆測資，每筆測資你的程式會有 $p$ 的機率答對，並且你做了 $k$ 次取最好的，請問你 AC 的機率是多少 - 一筆測資對的機率 $\rightarrow p$ - 單筆測資答錯：猜了 k 次全部都錯，機率是 $(1 − p)^k$ - 單筆測資答對：$1 − (1 − p)^k$ - 全部答對：$(1 − (1 − p)^k)^T$ ---- ## 生日悖論 假設一年有 365 天，班上有 $n$ 個人，有任兩個人生日相同的機率是多少？ Answer : ||$1-\frac{P^{365}_n}{365^n}$|| |||| ---- hash 的成功率跟這個悖論有關，附上[連結](https://zh.wikipedia.org/zh-tw/%E7%94%9F%E6%97%A5%E5%95%8F%E9%A1%8C)，有興趣可以看! --- ## 不一樣的 Hash ---- ## 以前教過的hash 在字串課教過 rolling hash，可以讓你把一個字串的子字串壓成一個數字 $h(s_1,s_2 . . . s_n) = (s_1 × C^{n−1} + s_2 × C^{n−2} + · · · + s_n)$ $mod$ $M$ ---- ## 以前教過的hash - 一樣的子字串，拿去做hash，出來的值一定一樣 - 但是一樣的 hash 值，映射回來的子字串**不一定**一樣 - 什麼會影響碰撞的機率？ ---- ## 例題 : 矩陣相乘 給你 $N*N$ 的矩陣 $A,B,C$，問你 $A \times B$ 是否等於 $C$ ? $N \le 10000$ ---- 暴力算矩陣乘法複雜度為 $O(n^3)$，就目前已知的計算矩陣乘法複雜度一定炸開，因此可以考慮對矩陣去做 hash ! ##### ~~什麼!!!矩陣可以拿來hash!!?~~ ---- ## 秉持 Hash 的精神，把矩陣 Hash 掉！ 以前教過的 hash 可以把一個 「子字串」 or 「子區間」 hash 成一個數值，再去判斷兩者是不是一樣 如果這時候可以把矩陣 Hash 成「某個東西」的話，好像就很好判斷$AB = C$ 了？ 設 $h$ 函數為可以把某矩陣 Hash 之後的變成某個東西的函數，所以要滿足： $h(AB) = h(C)$ 所以接下來要想個辦法算出 $h(AB)$ 和 $h(C)$.... ---- 對於以前學過的子區間 Hash ， 可以展開成以下 matrix 形式 設 $R = \left[\begin{matrix} c_0 \\ c_1 \\ : \\ c_n\\ \end{matrix}\right]$，$\left[\begin{matrix} a_0 & a_1 & ... & a_n\\ \end{matrix}\right] \times R = hash$ 值 子區間可以看成 $1 \times N$ 的 matrix ，對於每一項，乘以他對應的 base ，而得到 $1 \times 1$ 的 hash 值 那我們是不是也可以把一個矩陣 ($N \times N$ 的matrix) 壓成更小的矩陣 (?) ---- 因此考慮.... $\left[\begin{matrix} a_{00} & a_{10} & ... & a_{n0}\\ a_{01} & a_{11} & ... & a_{n1}\\ : & : & ... & :\\ : & : & ... & :\\ a_{0n} & a_{1n} & ... & a_{nn}\\ \end{matrix}\right] \times R = \left[\begin{matrix} hash_0 \\ hash_1 \\ : \\ hash_n\\ \end{matrix}\right]$ 這樣做可以把一個 $N \times N$的矩陣 hash 成 $N\times 1$ 的小矩陣了 因此問題變成 $(AB)R = CR$ ，交換一下矩陣計算順序 $\rightarrow ABR = CR$ $\rightarrow A(BR) = CR$ 這樣計算的複雜度為 $O(n^2)$ ---- 前面好像都沒講到 $R$ 矩陣裡面的數值具體要塞什麼？ 先別急，再觀察一個性質 - 如果 $AB = C$，則不論 $R$ 是什麼，等號一定成立 - 如果 $AB \neq C$，則不論 $R$ 是什麼，等號「不一定」成立 有這個性質可以幹嘛？ ||可以 random!!|| ---- 讓 $R$ 裡面所有的元素全部都是亂數生成的 考慮 $AB \neq C$ 的情況，思考一下會發現，等號「成立」的情況機率很低，直接去算 $A(BR)=CR$ 好像很大機率會過！ 不對啊！等號「成立」怎麼辦 $\rightarrow$ ||多做幾次!!|| ---- 多做幾次，讓WA的機率越乘越低，是 random 演算法的精神之一! ```cpp! while(time--){//做個 t 次，不要超過複雜度就好 1.隨機生成R矩陣 2.算A(BR) 3.算CR 4.如果ABR != CR -> "NO!!!!!" 5.如果ABR == CR -> 再做一次 } 做t次做完了，都沒問題 -> "YEESSSSSSS!!" ``` ---- 這裡我們學到了「二維Hash」,「生成隨機數把東西映射到其他東西(?)」的技巧，下面會再提更多 hash 的例子！ ---- ## 成雙成對 給妳一個長度為 $n$ 的序列 $a_1, a_2, ... ,a_n$，給你 $q$ 筆詢問，每筆詢問給你 $[l,r]$ 問你 $[l,r]$ 區間內是否每一種數字都出現偶數次， $1 \le n,q \le 10^6$ $a_i \le 2^{31} -1$ ---- 不可能 $O(nq)$ 暴力去算，太白癡了 但我們好像學過根號算法？ 複雜度 $O(n \sqrt n)$，好像還是不會過 ---- 這時候就要用隨機來~~唬爛~~了！ ---- 透過觀察，會發現一個好的區間 $[l,r]$，滿足$a_l$ $\oplus ...$ $\oplus$ $a_r = 0$ ex: ```cpp! 9, 1, [3, 5, 3, 5], 2 ``` 為什麼呢？因為相同的數字透過 Xor 的性質，兩兩互相打架抵銷成 0 ---- 但是也有情況 Xor 會爛掉 - Xor 的好情況： $a$ $\oplus$ $a =0$ - Xor 的不夠好情況 $1$ $\oplus$ $2$ $\oplus$ $3 =0$ 因此要避免這種情況發生，這時就要用到隨機ㄌ ---- 可以選擇把每個元素透過隨機打到 long long 範圍的任意數字， 由於我們把值域範圍從 「$2^{31}-1$」 打到 「$2^{64}-1$」 左右，使碰撞的機率降低，在這樣的序列下去找好的區間，$1$ $\oplus$ $2$ $\oplus$ $3 =0$ 的情況發生機率極低。 其實隨機就這樣，很唬爛，看起來超玄，但會過 :/ ---- ## K的倍數 這時題目變成... 給妳一個長度為 $n$ 的序列 $a_1, a_2, ... ,a_n$，給你 $q$ 筆詢問，每筆詢問給你 $[l,r]$ 問你 $[l,r]$ 區間內是否每一種數字都出現 $K$ 的倍數次， $1 \le n,q \le 10^6$ ---- 概念一樣，把所有元素打到任意一個隨機數，再去找好的區間 這時限制變成，每種數字都出現 $K$ 的倍數次，怎麽做？ ---- 上一題當中，對於同一種元素，我們讓他兩兩打架，打到最後讓他消失不見 那可以讓他們$k$$k$打架(?) ，一樣讓他們打起來，有兩種方法： 1. 設計一個 $\oplus_k$，代表 $k$ 進制的 xor 2. 用相加的，同一種元素讓他們加起來為0 顯然 1. 很好懂但很難實作，讓我們講講2. ---- 用相加的，我們假設一個區間裡面有 $k$ 個 $a$，我們可以把 $(k-1)$ 個 $a$ 打到 $+x$，第 $k$ 個 $a$ 設定成 $(k-1) \times (-x)$ ， 這樣可以使得這段區間的 $a$ 相加為 0 因此可以這樣構造新的序列： |序列| $c$|$a$|$a$|$c$|$c$|$b$|$c$|$b$|$b$|$a$| |---|----|---|---|---|----|---|---|---|----|---| |打到的數字|$+z$|$+x$|$+x$|$+z$|$-2z$|$+y$|$+z$|$+y$|$-2y$|$-2x$| 這樣就只要算區間和為零的子區間有多少就好了，因為是一個long long範圍的隨機數，所以「區間和為零但不是一個好的區間」的機率會非常小 --- 休息一下～ --- ## 讓你覺得「蛤？為什麼這樣做會AC」的例題們 * 眾數 * 最近點對 ---- ## 眾數 絕對眾數的定義：數字出現次數嚴格超過長度的一半 ---- 題目 be like : 給你長度為 $N$ 的序列，$q$ 筆詢問 每次詢問給出區間 $[l,r]$ ，詢問裡面的區間絕對眾數是誰? ---- 你會發現，在區間裡面戳一個數字，它會是區間絕對眾數的機率會有$\frac 1 2$ 所以我們只要戳30次 這樣連戳30次都不是眾數的機率是 ${\frac 1 2}^{30}$ 那要怎麼確認一個數字是不是區間絕對眾數呢? ---- 把每個數字的index記錄下來 然後使用二分搜去算它在此區間有幾個數字，就可以知道它是不是區間絕對眾數 因此複雜度是 $O(30 Q log N)$ ---- ## 變化題 給你一個長度為 $n$ 的 arr ，求出一個 MOD 讓這個 arr 有絕對眾數 要取模誒 那他怎麼可能可以隨機? 還真可以。 因為在 MOD 完之後他會是絕對眾數，因此你任選一個數字，它取模完會是眾數的機率是 $\frac 1 2$ 所以隨機挑選兩個數字，兩個都是眾數的機率是 $\frac 1 4$ ，然後枚舉 $|x-y|$ 的質因數 當成模數去計算即可。 ---- ## 分析 一次取到兩個都是眾數的機會是 $\frac 1 4$ 也就是說不是的機率是 $\frac 3 4$ 那我只需要 ${\frac 3 4}^T$ 就可以保證會是對的。 ---- ## 最近點對 給你平面上 $N$ 個點，對於任意 $(i,j)$， 點 $i$ 和點 $j$ 的歐幾里德距離最小值是多少？ ---- 以前有教過分治的算法，一直分左邊分右邊然後blablabla.... 但如果你有實作過的話，會發現最近點對分治超難寫，那我們試試隨機！ ---- - 假設現在有 $i-1$ 個點在平面上，而且知道前 $i-1$ 個點的最近距離為 $d$ - 如果距離變短，那最近點對的其中一個點一定是 $i$ - $i$ 周圍畫一個半徑為 $d$ 的圓內有其他點 - 但是要檢查半徑為 $d$ 的圓內有沒有其他點太難了 QQ ---- - 退而求其次，我們找到一些可能跟它距離小於 $d$ 的點 - 把整個平面切成 $(\frac{d}{2})$ × $(\frac{d}{2})$ 的網格 - 檢查所有 $i$ 所在的格子和周圍 8 格和再往外一圈共 25 格裡的點 - 如果找到距離小於 $d$ 的點，就把網格重畫 ; 否則把 $i$ 直接加進它在的那個格子裡  ---- 聽起來，我們這時想到的做法會是： - 先把兩個點放在平面上，以這個點對當做目前的最近點對，距離為 $d$ ，並用這個 $d$ 在平面上分割網格 - 對於第 $3$~$n$ 的點$i$，檢查點 $i$在網格上的附近25個點，如果有點並且這個點跟點 $i$ 可以更新 $d$： - 就：用這個新的最近點對重新畫網格 - 否則：放進網格內 算算看複雜度 ---- - 每個格子內最多只有 1 個點 => 最多只要檢查 25 個點 - 每次重畫格子要花 O(i) 的時間，不然加入只要花 O(1) 的時間（用 hash table） - 這樣總時間需要考慮重畫格子、放進方格的機率，大約是 $\sum$加入第 $i$ 個點花的時間 $=\sum(p_i × O(i) + (1 − p_i) × O(1))$ - $p_i$ = 第 $i$ 個點要重畫格子的機率 但測資一定非常嚴格，一定會構造要你一直重畫格子的測資，因此會退化成 $O(n^2)$ ---- 但如果我們把點都 random_shuffle 呢？ 既然現在 random 了，那複雜度一定會小於等於 $O(n^2)$ ，接下來就來算算看 random 後重新畫方格的機率 $p_i$ ---- 其實重新畫方格的機率就是 $O(\frac{1}{i})$，因此在shuffle之後複雜度會是： $\sum(p_i × O(i) + (1 − p_i) × O(1)) = O(n)$ 因此我們期望 $O(n)$ 就可以做完了 ---- ## 一些細節 1. 因為有些點座標會有負數，所以要事先把座標搬到第一象限 ```cpp! int mnx=1e18,mny=1e18; for(auto [x,y]:a){ mnx=min(mnx,x); mny=min(mny,y); } for(auto& [x,y]:a){ x-=mnx; y-=mny; } ``` 2. 為了好好分割網格，你可能會砸 map ，但是在值域很大 (ex:1e9,1e16)的時候還是乖乖做分治，不然map會炸掉QQ 3. ~~如果不信任 map 的話，也可以自己寫一個 hash~~ --- [練習題單 ](https://vjudge.net/contest/676813) 唬爛吧！