信息學奧賽之數學一本通

《信息學奧賽之數學一本通》是2016年東南大學出版社出版的圖書，作者是林厚從。

內容簡介

N.Wirth給出了程式設計的一個重要公式，程式=算法+數據結構。

作為一個程式設計師或者程式設計愛好者來說，不應該只把程式設計作為一門技術，更應該看成是一種藝術。其實，算法本身也是一門藝術，數據結構本身也是一門藝術。程式也好，算法也好，數據結構也好，其中都蘊涵了很多的數學，而數學更是一門藝術。如果把數學與程式設計完美地結合在一起，則是藝術的巔峰！

從某種意義上來說，計算機源於數學。而作為計算機科學核心技術的程式設計，與數學之間的關係更是密不可分，可以這樣說，數學是電腦程式設計的靈魂。利用數學方面的知識、數學分析的方法以及數學解題的技巧，可以使得程式設計變得輕鬆、美觀、高效，而且往往能反映出問題的本質。

在ACM國際大學生程式設計競賽（ACMICPC）和全國青少年信息學奧林匹克競賽（NOI）系列活動中，越來越多地出現了數學的影子，也用到了越來越多數學方面的知識，對選手的數學修養要求越來越高。本書的目的就在於給廣大編程愛好者和信息學參賽者，介紹和總結一些程式設計中常用的數學知識和數學方法，希望能起到拋磚引玉的作用。

目錄

第1章數論1

1.1整除2

1.2同餘6

1.3最大公約數9

1.31輾轉相除法9

1.32二進制算法9

1.33最低公倍數10

1.34擴展歐幾里得算法10

1.35求解線性同餘方程11

1.4逆元*本書中加“*”號內容為提高性知識，一般在省隊選拔及NOI比賽中才會涉及。16

1.5中國剩餘定理*20

1.6斐波那契數23

1.7卡特蘭數29

1.8素數32

1.81素數的判定33

1.82素數的相關定理35

1.83MillerRabin素數測試*36

1.84歐拉定理37

1.85Pollard Rho算法求大數因子*38

1.9BabyStepGiantStep及擴展算法*46

1.10歐拉函式的線性篩法*54

1.11本章習題57

第2章群論*64

2.1置換64

2.11群的定義64

2.12群的運算64

2.13置換65

214置換群65

2.2擬陣65

2.21擬陣的概念66

2.22擬陣上的最最佳化問題67

2.3Burnside引理69

2.4Polya定理72

2.5本章習題86

第3章組合數學91

3.1計數原理91

3.2穩定婚姻問題*101

3.3組合問題分類107

3.31存在性問題108

3.32計數性問題108

3.33構造性問題109

3.34最最佳化問題110

3.4排列110

3.41選排列110

3.42錯位排列113

3.43圓排列113

3.5組合116

3.6母函式*129

3.61普通型母函式130

3.62指數型母函式132

3.7莫比烏斯反演*142

3.8Lucas定理*150

3.9本章習題155

第4章機率163

4.1事件與機率163

4.2古典機率165

4.3數學期望171

4.4隨機算法181

4.5機率函式的收斂性*189

4.6本章習題197

第5章計算幾何203

5.1解析幾何初步203

5.11平面直角坐標系203

5.12點204

5.13直線204

5.14線段205

5.15多邊形205

5.16圓206

5.2矢量及其運算213

5.21矢量的加減法213

5.22矢量的數量積213

5.23矢量的矢量積214

5.3計算幾何的基本算法220

5.4平面凸包236

5.5旋轉卡殼*243

5.51計算距離244

5.52外接矩形248

5.53三角剖分250

5.54凸多邊形屬性254

5.6半平面交*264

5.7離散化272

5.8本章習題278

第6章矩陣297

6.1矩陣及其運算297

6.11矩陣的基本運算298

6.12矩陣的乘法運算299

6.13矩陣的行列式299

6.14矩陣的特殊類別300

6.2數字方陣309

6.3線性方程組及其解法314

631高斯消元法314

632LU分解法318

6.4MatrixTree定理*327

6.5本章習題336

第7章函式347

7.1函式的基本知識347

7.11函式的特性348

7.12常見的函式類型350

7.2函式的單調性354

7.3函式的凹凸性361

7.4SG函式365

7.5快速傅立葉變換*368

7.6快速數論變換*373

7.7本章習題379