# 隨機
:::spoiler 目錄
[TOC]
:::
# 社團discord
本學期電研社分兩班，這邊上雜學，另一班上機器學習，如果想要上機器學習的話現在可以去隔壁（廁所旁邊那一間）
## 什麼是隨機
數學、機率和統計領域使用隨機性的正式定義，通常假設存在某種分布，通常是均勻分布(uniform distribution)，也就是說，對於他值域內的所有數字，出現機率都是相等的。
以擲骰子來說，出現1, 2, 3, 4, 5, 6的機率都是$\frac{1}{6}$。
## 如何產生隨機
在前面我們以骰子為例，但是仔細想想，骰子出現的數字**真的是隨機的嗎?**
實際上，骰子出現的數字受到擲出的力度、角度、空氣阻力、摩擦力影響，嚴格而言，這是可以被計算出來的，而且也能夠控制出現的數字。但我們還是叫他**隨機**因為變因非常多且難以計算。
> 偽隨機性:一個過程似乎是隨機的，但實際上並不是。
在電腦上我們也可以藉由實作很複雜的函數來生成偽隨機數
:::warning
如果自己寫的話，要注意運算後是否依然為uniform distribution，例如兩隨機數直接相加就不是
:::
### 梅森旋轉演算法
```python=
def _int32(x):
return int(0xFFFFFFFF & x)
class MT19937:
def __init__(self, seed):
self.mt = [0] * 624
self.mt[0] = seed
self.mti = 0
for i in range(1, 624):
self.mt[i] = _int32(1812433253 * (self.mt[i - 1] ^ self.mt[i - 1] >> 30) + i)
def extract_number(self):
if self.mti == 0:
self.twist()
y = self.mt[self.mti]
y = y ^ y >> 11
y = y ^ y << 7 & 2636928640
y = y ^ y << 15 & 4022730752
y = y ^ y >> 18
self.mti = (self.mti + 1) % 624
return _int32(y)
def twist(self):
for i in range(0, 624):
y = _int32((self.mt[i] & 0x80000000) + (self.mt[(i + 1) % 624] & 0x7fffffff))
self.mt[i] = (y >> 1) ^ self.mt[(i + 397) % 624]
if y % 2 != 0:
self.mt[i] = self.mt[i] ^ 0x9908b0df
```
### seed
作為函數的初始參數，通常是用電腦的時間
```cpp=
// 記得 #include<chrono>
chrono::steady_clock::now().time_since_epoch().count()
```
## C++的隨機
### std::rand()
```cpp=
srand(chrono::steady_clock::now().time_since_epoch().count());//seed，這一行不打的話預設為1
cout<<rand()<<endl;
```
有很多缺點
* 在windows系統上值域只有到32767
* 缺陷很多
### mt19937
```cpp=
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
cout<<rnd()<<endl;
```
如果要限制值域的話可以自己取模或者
```cpp=
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> dis(0, 1e9);
//uniform_real_distribution<double> dis(0, 1e9);
cout<<dis(rnd)<<endl;
```
也有其他種分布可以用，[這裡](https://cplusplus.com/reference/random/)有很多。
### shuffle
```cpp=
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
vector<int> v={1,2,3,4,5};
shuffle(v.begin(),v.end(),rnd);
```
## 唬爛
有時候可以應用題目的特性去得到一個好的算法，例如有些題目會跟你說測資是隨機生的，有一些題目測資品質很差(例如能競校內賽)，或者沒有全對也有分數(例如能競區賽)
### [D. Problem with Random Tests](https://codeforces.com/problemset/problem/1743/D)
給你一個隨機生成的01字串$s$，求從$s$中選出兩個可重疊的子字串$s_1$、$s_2$的最大OR。
首先，不失一般性假設$|s_1|\geq |s_2|$，$s_1$一定可以選原本的字串去掉前綴0。
證明：把兩個01字串作OR運算，把比較長的那個字串變長，運算結果一定會變大。
接著，我們會希望$s_1$的第1個0變成1，那麼$s_2$會有以下條件：
1. 第一位是1
2. 長度等於 $s_1$的第一個0到末端的長度
只要枚舉符合條件的子字串就好了，這樣的子字串有幾個呢？
（$s_1$第一個0前面1的數量）個！
會發現這個數字通常很小，因為測資是隨機生的，所以有一長串1的機率很小。
### 數的分解
來自2023能競校內賽、2010 ISSC 第6次模擬賽
給你一個數字$N$，由小到大輸出盡量少的質數，使得這些質數的和等於$N$，並在滿足前項條件下使這些質數的乘積最大。
* $2\leq N\leq 10^6$
* 多筆測資但沒跟你講範圍
首先試試看一些小測資，會發現似乎最多只要3個質數就可以湊出所有數字。(實際上目前沒有任何反例，詳見[哥德巴赫猜想](https://zh.wikipedia.org/zh-tw/%E5%93%A5%E5%BE%B7%E5%B7%B4%E8%B5%AB%E7%8C%9C%E6%83%B3))
藉由通靈，可以分成以下case:
1. N是質數
2. N是偶數，N=質數+質數
3. N是奇數，N=2+質數
4. N是奇數，N=質數+質數+質數
對於1.和3.可以利用埃式篩預處理達到$\text{O}(1)$查詢(之後可能會教)，
對於2.和4.我們可以想像這些質數大機率會很接近(為了讓乘積最大)，那麼我們不妨假設一個唬爛常數$hulan$，如果要把$N$切成三個質數，就暴力枚舉$\frac{N}{3}$的前後$hulan$個質數中的其中兩個質數$a,b$，再選$N-a-b$也是質數且乘積最大的那一組。
單筆複雜度$\text{O}(hulan^2)$
但還有一個問題是，我不知道有幾筆測資啊?
沒關係，就相信他不會太多。
賽後去看了測資，發現他只有2組測資，一組只有5筆==
這時可以引用GrandTiger說的一句話:
> 要相信 $\text{O}(很快)$
## 題目
### [區間絕對眾數](https://neoj.sprout.tw/problem/794/)
### 成雙成對
給一個長度為$N$的陣列$A$，回答下列詢問$Q$次:
給$L$與$R$，問$A_L, A_{L+1}, A_{L+2} ,\dots, A_{R}$內的每個數字是否都出現偶數次?
* $N,Q\leq 10^6$
* $A_i\leq 10^9$
看到出現偶數次就要想到，任兩個相同的數字XOR起來一定會是$0$。
那麼就可以想到一個很簡單的做法:如果$A_L$到$A_R$的區間XOR是$0$，就輸出YES，反之則輸出NO，可以搭配前綴和在$\text{O}(1)$時間內回答。
但，考慮以下的case:
$\{ 1,2,3\}$的XOR為$01_{(2)}\oplus 10_{(2)}\oplus 11_{(2)} = 0$，但並不符合題目要求。
這時可以將每個數字隨機映射到某個很大的數字，因為我們只在乎同個數字出現的次數，而非數字本身。可以相信這麼做的話出現上面反例的機率很小。
另外一個取代XOR的方法是，紀錄每個數字目前出現奇數次還是偶數次，若出現奇數次就把他加上負號，詢問時檢查區間合是否等於0。例如：
$\{7, 9, -9, -7\}$
### [c120: 張皓晴的笑話 AI](https://judge.tcirc.tw/ShowProblem?problemid=c120)
### [D. Cut and Stick](https://codeforces.com/problemset/problem/1514/D)
### [想不到題目標題QQ](https://neoj.sprout.tw/problem/793/)
Sign in with Wallet
Connect another wallet