owned this note   changed 4 months ago  
Published Linked with GitHub

random

  • 要怎麼random(產生亂數)
  • random可以用在哪裡
  • 想辦法靠賽

產生亂數

在數學意義上並沒有真正的亂數，因此都只能用時間種子或者是怪怪的公式去假裝亂數
所以我們今天使用的是時間種子

chrono::steady_clock::now().time_since_epoch().count()

那記得使用這個要引入標頭檔

#include<chrono>

這是一個單位以 ms 來計算的時間亂數

那我們分析一下這是什麼，大家就不用自己去找了

chrono::steady_clock::now().time_since_epoch().count()

首先 \(steady\_clock\) 是一個單調的時鐘
然後 \(now()\) 就是指現在的時間
接著 \(time\_since\_epoch()\) 是指 現在獲取的 \(now\) 到時間元年的間隔
最後 \(count()\) 當然就是指有幾個間隔

*時間元年 1970/01/01

再來是產生器，我們會使用到的是 mt19937

什麼是mt19937呢，背後支持的數學演算法是梅森旋轉算法，可以使得在一個範圍內有隨機分布。

那要怎麼產生呢?

mt19937 變數名稱(亂數種子);

所以我們的定義就會變成

mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());

那我們就可以開始利用mt了

那因為mt是我們的產生器，我們還需要給他一個分布的範圍

uniform_int_distribution<> dis(0, 1e9);

那他的預設值就是int 如果今天要用小數點的話就分別是以下

uniform_int_distribution<int> 分布變數名稱(最小值, 最大值);
uniform_real_distribution<double> 分布變數名稱(最小值, 最大值);

所以最後就會這樣寫出東西

#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 阿

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\) 就可以保證會是對的。

練習題單

這種東西只能找機率XD

Select a repo