關於常數

FHVirus 2021-11-10

鴨腸

拜託不要像我一樣沉迷於壓常和 TIOJ Topcoder。

首先先放幾個重要的觀念。

cin cout 其實很有效率也很乾淨，雖然時間上不一定最快。
除法和模運算很慢，尤其是模變數的時候。
使用大空間又不連續存取的時候會影響到時間。真的。
std::vector 對於執行速度的影響取決於使用方式。
把程式寫的乾淨簡潔遠比硬壓常數重要；簡單的程式碼通常常數不會太糟。

以下會一一解說。

1. `cin cout` 其實很有效率

在加了 ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 之後，cin cout 其實就足夠應付絕大多數的題目了。我在壓常的時候常常使用快速輸入輸出，但那通常不會讓一題從 TLE 變成 AC。是一個非必要的技巧，看過一遍知道怎麼做就好。

如果你想學，我寫過一篇介紹了，請點這裡並斟酌使用。

實用度： 0。在賽中從來沒用過。

2. 除法和模運算很慢

先看例子吧：TIOJ 1306 字串中的字串。
這題的 hash 作法會需要蠻多的模運算，可以自行試試看在模的質數前面加或不加 const 的時間差別。

網路上有人測試出來，如果把整數加法和位元運算當作一單位時間，那整數乘法大概是兩單位，整數除法和模運算則是 21 單位。
同理，浮點數和開根號超慢，在做計算幾何算距離的時候存 long long 都比開根號好很多（還可以避免精度問題）。
再同理，cmath 裡面會用到浮點數的函式常數都不小，能少運算幾次就少運算幾次。請注意，並不是不要用，是減少不必要的呼叫次數。

回到除法和取模，簡而言之就是「減少不必要的使用次數」，也可以寫成下面這樣的形式：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


typedef long long ll;
const int MOD = 1e9+7;
inline int madd(int u, int v){
	u += v - MOD;
	// 等價於：
	// if(u < 0) u += MOD;
	u += MOD & (u>>31);
	return u;
}
inline int mmul(int u, int v){
	return (ll) u * v % MOD;
}

這樣寫會讓運算變得比較容易閱讀（個人覺得），常數也不會太大，也不用小心翼翼的估會不會爆 long long。
特別是加法，不用每次都取模。想知道它在做什麼的話，可以去研究補數表示法。

如果你覺得正常除、模一個常數還是太慢，可以考慮去學 Barrett Reduction。例題：TIOJ 1768。 TIOJ 1064 的 NTT 也可以用這個技巧加速。

實用度：3。除了常數之外，我特別推薦上面的寫法，因為有人校內賽被模運算搞，改成上面寫法就過了。
請小心處理（跟常數無關）。

3. 空間存取

首先，記憶體大致上（非常粗略的）可以被想像成這樣：

記憶體是一個超長的一維跑道。
陣列是這條跑道上的連續某一區段（二維的就是很多個排在一起的區段）。
電腦是一個人站在上面，永遠面對正向。
當電腦要存取某個位置的時候，他就要慢慢跑過去那邊。

可以用歪理得出一些結論：

連續存取一段會比隨機順序亂戳要來的快（不用折返跑）。
正著讀會比逆著讀快（你到著跑試試看）。
簡單的暴力 For 迴圈其實蠻快的（因為通常都是順順掃過去）。
在要遍歷的陣列大小超大的時候，char、short 會比 int 快。
滾動 DP 會比開滿還要快。
改變迴圈順序也許會變快（下面影片有講）。

如果你想要深入了解 Locality 還有 Cache miss 之類的，可以去看看 CPU 架構，或是看看這部影片。

例題：TIOJ 1090 Grazing on the Run。
當初我去問 ZCK 那時的 Topcoder 怎麼跑那麼快的，ZCK 就和我說：「你有聽過滾動 DP 嗎？」他是認真問的，但感覺就很嘲諷 XD

實用度： 1。知道這些有時候還是有點用。

4. `std::vector` 其實不慢

一般情況下會 vector 導致常數變大都是因為他會動態的要空間（細節請自行研究）。如果你已經知道你的 vector 會開多大了，那先開好或是使用 reserve 函式都是不錯的選擇（後者也適用於其他 STL container）。

舉例來說，建一棵樹的鄰接串列的時候，會有 $n$ 個 vector 輪流要空間，但實際上只要大約 $2n$ 的空間就足夠了。
想要壓這個的話，可以去學前向星（或叫做 linked list 存圖，中國人常用）。
雖然我有很多 Topcoder 是靠這個搶的，但它會導至前面提到的記憶體不連續存取，不一定會比較快，各有利弊。

再來說說 vector 會比較快的例子。

在做樹背包的時候，一個作法是把所有節點的背包存起來，然後一個一個取。
這樣一樣會被第三點提到的東西卡掉，導致時間和空間都頗大。
這時候考慮每次都只在遞迴到的時候開區域，做完 return 回去；
這樣不只省空間，也可以讓時間變快。也許 vector 有某種分配空間的黑魔法。
例題：TIOJ 2199 大促銷改，比較慢的那筆完全沒有壓常。

實用度： 8e7。好好用 vector 雖然會大多數時候會慢一點，但是其實還不錯（根本就自己在推銷）。 ~~還可以避免測資大小寫錯找不到 bug~~

5. 壓常不重要

如題，寫出乾淨的扣的、想題比較重要。
壓常就像刷水題一樣沒營養，請不要讓壓常佔用寫好題目的時間。
不會做題目會壓也沒用……除非你真的賽中壓的過 $N, Q \le 10^5$ 的 $O(NQ)$。

6. 雜燴

關於 `#pragma`

大致上可以理解成讓編譯器幫你處理壓常的事情。我沒有深入研究，但模板理常駐 #pragma GCC optimize("Ofast")。有些題目沒差，但大部分都會有感的變快，有些甚至可以差到三、五倍。

實戰壓常

例：TIOJ 1937。

這題我用了快速輸入輸出＋優化迴圈順序＋把矩陣用 short 和 char 存＋神奇#pragma。就像前面所說，簡單迴圈優化後超級快。

偽指標

在要重複開多棵資結的時候，偽指標會讓空間使用變得比較有效率。
通常我會寫一個 newNode() 函式，讓他跟 new 做一樣的事情。

遞迴減肥

分治遞迴到夠小的時候就可以用暴力迴圈做，因為簡單迴圈真的很快。
例：TIOJ 2213 花枝遊戲。我用偽指標資結＋分治減肥就很快了。
好處是我可以偷懶不處理分治邊界狀態。

關於 ZKW

快，但不必要，因為寫起來沒有比較快（賽中不太實用）。
可以學起來但不要過度依賴。

關於潮汐

同一份程式碼上傳多次可能拿到不同的執行時間、空間。我喜歡叫他潮汐。 TIOJ 的漲退潮差平常應該是 20 ~ 40 kB 左右，不過賭那個潮汐不如去寫題。

賽中？

我會說大概不需要以上任何東西（我自己也沒用過），頂多 #pragma 加暴力賭會不會過、好好取模避免爆炸。

以上大概是我所有壓常的技巧了。有想到再補。
有錯誤、疏漏的話還請大家不吝指教 ><