<style> .reveal .slides { text-align: left; font-size:28px; } </style> ## random --- * 要怎麼random(產生亂數) * random可以用在哪裡 * 想辦法靠賽 ---- ## 產生亂數 ---- 在數學意義上並沒有真正的亂數，因此都只能用時間種子或者是怪怪的公式去假裝亂數 所以我們今天使用的是時間種子 ```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; } ``` --- ## random 可以用在哪裡? ---- * shuffle() ---- 就 shuffle 阿 ```cpp shuffle(arr,arr+n,mt); ``` 跟sort的用法一樣，代表直接把你的arr全部打亂 就這樣。 --- ## 想辦法讓你靠賽是對的 * MOD * 眾數 ---- ## MOD 如題 MOD 2 的話，那就隨機兩次(X ---- ## 眾數 *絕對眾數 數字出現次數超過長度的一半 ---- 給你長度為N的 arr，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$ 就可以保證會是對的。 --- [練習題單 ](https://vjudge.net/contest/598374#problem/D) 這種東西只能找機率XD