Mathematics
前言
「寫程式是否需要數學能力好？」和「寫程式是否需要英文能力好？」一樣，是經常爭論不休的問題。
以一般論來說並不一定，畢竟寫程式的目的有很多種，包含但不僅限於寫靜態網站、維護資料庫、預測股價……等等。
然而，以競技程式設計來說，答案卻是顯而易見的，需要數學。
不幸的是，數學對許多人來說是個難解的罩門，包含了筆者本人，就是因為自認為數學能力比不上他人，因此才轉戰競程。
如此一來，難道就成了死胡同，面對難攻不破的高牆最終只能鎩羽而歸嗎？也並非如此。
競程與數學競賽中所用的數學，最大的差別就在於，競程中的數學無須證明……這樣說又太過頭。
更為清晰的說法應該是，競程中用到的數學，相較於數學競賽中的數學，較為不抽象。
數學競賽強調如何證明解的存在、如何找到解。
而競程則偏重如何以有效率的方式來解決問題。
因此數學競賽中用到的技巧對許多人來說很抽象，盯著題目良久卻依然不知如何下手。
但是競程中通常是有個具體的情境，而我們的課題是要如何使用數學工具加速尋找解。
結果就是，追尋真理的數學競賽中的數學會傾向抽象，為具體情境服務的競程中的數學會相對容易想像。
但要注意的是，這只是以二分下所作的結論，實際上兩者的交集仍是很大。
舉例來說，用來判斷二分圖的著色法在數學競賽、競程中都有著用武之地。
對競程的有志之士們還請不要畏懼數學。只有面對之後，才能夠決定要戰鬥、還是要逃避。
分類
一般來說，數學領域分為四個 - ACGN。
- Algebra 代數
- Combinatorics 組合
- Geometry 幾何
- Number 數論
代數
代數的基礎是線性代數，包含了多項式、向量、矩陣……等內容。
著名的 FFT 也是以線性代數作為基礎而發展出的算法。
相對的，有線性代數，也有非線性代數，像是群、環、體等等。
不過非線性代數屬於進階的內容，除了群論以外，在競程中幾乎不會出現。
組合
組合是探討物體間的結構與性質的學問。
包含高中課程中所教到的排列、計數……等等。
在競程中，這類問題通常較為瑣碎，需要謹慎處理。
更進階的內容中會牽扯到群論。
幾何
在競程中通常不會將其歸類在數學中，而是歸類在計算幾何之中。
數論
數論包含了對質數、公因數……等等數字的性質的研究。
作為赫赫有名的就是歐幾里得的輾轉相除法，就是數論中重要的演算法。
對選手來說，這類問題通常較為燒腦，也顯得較為玄學。
當然，分類是死的，而問題是活的。
一道問題可能還需要搭配不同競程解題技巧才能解決。
舉例來說，計數問題可能需要 DP、數論問題需要分塊……等等。
因此上述分類就做個參考即可。
學習
或許有些人會認為競程中的數學和數學競賽一樣全都是玄學，因而避而不碰。
但如前述所言一樣，並非如此。
作為競程中數學問題的兩大分支的線性代數、組合，裡面用到的知識多來自於高中數學。
像是多項式、矩陣、C 幾取幾……等等。
因此做為基礎，只要學好高中數學，再輔以一些競程的知識，其實就能夠有效解決諸多競程中的數學問題了。
但若說到進階，還是做好每碰一個主題，就有一次學習陣痛期的準備比較好。
總結
數學是重要的。
從分析複雜度、理解其他算法這種基礎的層級。
到 FFT、杜教篩等進階內容中，數學無處不在。
縱然忽視數學依然能成為實力不俗的選手，但也僅此而已，難以繼續突破。
隨著學問加深、問題變得艱鉅，就會越發考驗選手的數學直覺。
又或者，到最後會發現一切競程領域，不管貪心、DP、資料結構……等等都是殊途同歸，條條大路通數學、大家都只是數學變換形式的存在。
當然，對於初學者而言，選擇簡單、容易理解的章節下手，不失為一個良策。
但最終，要推倒高牆，就只能主動碰觸高牆。
基礎主題
這裡列出一些競程中會用到、且相對基礎的數學主題。
- 數論
- 質數和因數
- 篩法
- 模運算
- 組合
- 二項式定理
- 卡特蘭數
- 排容原理
- 矩陣
- 線性遞迴
- 高斯消去法
- 其他
- 機率 - 期望值
- 賽局 - NIM 遊戲
資源
待補