分享幾個(gè)第一次看到就被它的優(yōu)美深深震撼到的代碼：

1、線性求逆元：

for (int i = 2; i < MAXN; i++)
    inv[i] = mul(inv[mod%i], mod - mod / i, mod);
復(fù)制代碼

僅僅兩行代碼，就實(shí)現(xiàn)了在的時(shí)間內(nèi)求出1到n對(duì)模m的逆元有木有??？

2、求最大公因數(shù)：

int gcd(int x, int y){return y ? gcd(y, x%y) : x;}
復(fù)制代碼

第一次接觸到這樣的代碼時(shí)，我的內(nèi)心是這樣的：

wtf???黑人問(wèn)號(hào).jpg

3、樹狀數(shù)組

對(duì)于單點(diǎn)修改區(qū)間求和，樹狀數(shù)組可謂達(dá)到了時(shí)空復(fù)雜度的極限，甚至不多用額外一字節(jié)存儲(chǔ)空間。來(lái)看看它的實(shí)現(xiàn)：

修改：

void add(int i, int x){
    for (;i <= n; i += i & -i)tree[i] += x;
}
復(fù)制代碼

查詢：

int sum(int i){
    int ret = 0;
    for(; i; i -= i & -i)ret +=tree[i];
    return ret;
}
復(fù)制代碼

表示記性不好的我看完一遍也記住了呢。

4、zkw線段樹

對(duì)于單點(diǎn)修改區(qū)間查詢的線段樹，zkw大神實(shí)力教你如何1分鐘內(nèi)碼出代碼：

修改：

void set(int x, int value){
    val[x += treeLen] = value;
    while (x >>= 1)pushUp(x);
}
復(fù)制代碼

查詢：

int query(int l,int r){
    int ret = 0;
    for (l += treeLen - 1, r += treeLen +1; l ^ r ^ 1; l >>= 1, r >>= 1){
        if (~l & 1)ret = min(ret, val[l^1]);
        if (r & 1)ret = min(ret, val[r ^ 1]);
    }
    return ret;
}
復(fù)制代碼

以上都是一些十分基礎(chǔ)但真的讓你贊不絕口的算法和數(shù)據(jù)結(jié)構(gòu)。還有一些稍微復(fù)雜一些的栗子，由于手機(jī)碼代碼太不方便了，就以后再更吧。（如果有筆誤打錯(cuò)的地方歡迎指正哈）

5、后綴數(shù)組的DC3算法，反正學(xué)完它的一瞬間我是明白了，天才和普通人的智商差距簡(jiǎn)直比人和狗還大啊。。。

6、快速傅里葉變換的數(shù)論版本（即NTT）：學(xué)完后有種想去數(shù)學(xué)系的沖動(dòng)（還好后來(lái)冷靜下來(lái)了）。費(fèi)馬素?cái)?shù)群的性質(zhì)居然和復(fù)數(shù)完美吻合，不得不說(shuō)是一種奇跡啊。

7、主席樹：這是fotile巨佬考場(chǎng)上發(fā)明這種數(shù)據(jù)結(jié)構(gòu)，用于在的時(shí)間復(fù)雜度內(nèi)解決序列區(qū)間第k大問(wèn)題，以及區(qū)間內(nèi)元素的排名。個(gè)人感覺他比劃分樹的設(shè)計(jì)巧妙多了，有一種自然的美感。

8、Pollard因數(shù)分解算法：如果你真的把關(guān)于時(shí)間復(fù)雜度的證明一步步看完后，相信你會(huì)有一種豁然開朗的感覺。這個(gè)算法真正高的地方在于把生日悖論和遞推式循環(huán)節(jié)巧妙的結(jié)合在一起，最后運(yùn)用遞推方程主定理的理論，使得時(shí)間復(fù)雜度達(dá)到了看似不可能的期望的數(shù)量級(jí)。

其實(shí)現(xiàn)在感覺一切和數(shù)據(jù)結(jié)構(gòu)或數(shù)學(xué)有關(guān)的算法都是非常優(yōu)美的，前者在于設(shè)計(jì)的精巧性，后者在于證明的環(huán)環(huán)相扣，達(dá)到引人入勝的效果。

[圖片上傳失敗...(image-e02dfd-1574858434160)]