分享幾個第一次看到就被它的優美深深震撼到的程式碼:
1、線性求逆元:
for
(
int
i
=
2
;
i
<
MAXN
;
i
++
)
inv
[
i
]
=
mul
(
inv
[
mod
%
i
],
mod
-
mod
/
i
,
mod
);
僅僅兩行程式碼,就實作了在$O(n)$的時間內求出1到n對模m的逆元有木有!?
2、求最大公因數:
int
gcd
(
int
x
,
int
y
){
return
y
?
gcd
(
y
,
x
%
y
)
:
x
;}
第一次接觸到這樣的程式碼時,我的內心是這樣的:
wtf???黑人問號.jpg
3、樹狀陣列
對於單點修改區間求和,樹狀陣列可謂達到了時空復雜度的極限,甚至不多用額外一字節儲存空間。來看看它的實作:
修改:
void
add
(
int
i
,
int
x
){
for
(;
i
<=
n
;
i
+=
i
&
-
i
)
tree
[
i
]
+=
x
;
}
查詢:
int
sum
(
int
i
){
int
ret
=
0
;
for
(;
i
;
i
-=
i
&
-
i
)
ret
+=
tree
[
i
];
return
ret
;
}
表示記性不好的我看完一遍也記住了呢。
4、zkw線段樹
對於單點修改區間查詢的線段樹,zkw大神實力教你如何1分鐘內碼出程式碼:
修改:
void
set
(
int
x
,
int
value
){
val
[
x
+=
treeLen
]
=
value
;
while
(
x
>>=
1
)
pushUp
(
x
);
}
查詢:
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
;
}
以上都是一些十分基礎但真的讓你贊不絕口的演算法和數據結構。還有一些稍微復雜一些的栗子,由於手機碼程式碼太不方便了,就以後再更吧。(如果有筆誤打錯的地方歡迎指正哈)
5、字尾陣列的DC3演算法,反正學完它的一瞬間我是明白了,天才和普通人的智商差距簡直比人和狗還大啊。。。
6、快速傅立葉變換的數論版本(即NTT):學完後有種想去數學系的沖動(還好後來冷靜下來了)。費馬質數群的性質居然和復數完美吻合,不得不說是一種奇跡啊。
7、主席樹:這是fotile巨佬考場上發明這種數據結構,用於在$O(log n)$的時間復雜度內解決序列區間第k大問題,以及區間內元素的排名。個人感覺他比劃分樹的設計巧妙多了,有一種自然的美感。
8、Pollard因數分解演算法:如果你真的把關於時間復雜度的證明一步步看完後,相信你會有一種豁然開朗的感覺。這個演算法真正高的地方在於把生日悖論和遞推式迴圈節巧妙的結合在一起,最後運用遞推方程式主定理的理論,使得時間復雜度達到了看似不可能的期望$n^0.25$的數量級。
其實作在感覺一切和數據結構或數學有關的演算法都是非常優美的,前者在於設計的精巧性,後者在於證明的環環相扣,達到引人入勝的效果。