信息奧賽中的數(shù)學(xué)方法

1、目錄 l 基礎(chǔ)數(shù)論 l模意義下的運(yùn)算 l費(fèi)馬小定理、歐拉定理與乘法逆元 l快速冪與快速乘法 l輾轉(zhuǎn)相除法與高精度GCD l線性同余方程與拓展歐幾里得算法 l篩法與質(zhì)因數(shù)分解 l 組合數(shù)學(xué)入門 l排列與組合 l常用公式 l簡(jiǎn)單的組合數(shù)取模 l常用數(shù)列 l容斥原理與禁位排列 l 位運(yùn)算及bitset 基礎(chǔ)數(shù)論 BASIC NUMBER THEORY 基本概念 帶余除法 模數(shù)、取模 同余 因子 互質(zhì) 最大公因數(shù) 模意義下的運(yùn)算 很多題目的基礎(chǔ) 加減乘法在模意義下封閉 除法則不同 費(fèi)馬小定理 歐拉定理 乘法逆元 一些大質(zhì)數(shù) 快速冪 快速冪 快速冪：代碼 快速乘法 最大公因數(shù)（GCD） 更相減損術(shù) 輾轉(zhuǎn)

2、相除法 輾轉(zhuǎn)相除法：代碼 高精度加減乘法 高精度除法 高精度GCD 線性同余方程 拓展歐幾里得算法 拓展歐幾里得算法 拓展歐幾里得算法 拓展歐幾里得算法：代碼 求解線性同余方程 分解質(zhì)因數(shù) 枚舉因子 篩法 篩法 基礎(chǔ)數(shù)論： 例題 BASIC NUMBER THEORY: EXAMPLES NOIP2012 D2T1 同余方程 題面題解 拓展歐幾里得的直接應(yīng)用。 也可以直接算逆元。 POJ1061 青蛙的約會(huì) 題面題解 HDU2824 The Euler Function 題意題解 POJ2480 Longges Problem 題意題解 SGU106 The Equation 題意題解 進(jìn)一步

3、了解 組合數(shù)學(xué)入門 INTRODUCTORY COMBINATORICS 基本計(jì)數(shù)原理 加法原理 乘法原理 減法原理 計(jì)數(shù)問(wèn)題 統(tǒng)計(jì)滿足某些條件的物體的個(gè)數(shù)。 例： 求項(xiàng)鏈的本質(zhì)不同的染色方案數(shù) 求圖的不同生成樹(shù)的個(gè)數(shù) 答案通常很大，需要取模輸出。 兩個(gè)要點(diǎn)： 不重、不漏 排列與組合 Pascal公式 常用公式 常用公式 常用公式 證明的兩種方式 1. 組合學(xué)推理 2. 數(shù)學(xué)推導(dǎo) 嘗試一下證明 模意義下的組合數(shù) Catalan數(shù)列 Catalan數(shù)列 Bell數(shù)列 容斥原理 錯(cuò)位排列 禁位排列 組合數(shù)學(xué)入門： 例題 INTRODUCTORY COMBINATORICS: EXAMPLES 一道

4、數(shù)學(xué)題 題面題解 POJ3421 X-factor Chains 題意題解 URAL1860 Fiborial 題面題解 POJ3088 Push Button Lock 題面題解 無(wú)名試題1 題面題解 組合數(shù)學(xué)習(xí)題8.5 題面題解 SKI 題面題解 進(jìn)一步了解 位運(yùn)算與bitset BITWISE OPERATIONS AND STD:BITSET 位運(yùn)算 集合的二進(jìn)制表示 適用于全集大小比較?。ㄍǔＴ?2以內(nèi)）的情況。 用一個(gè)unsigned int表示一個(gè)子集。 二進(jìn)制位為1代表子集中有這個(gè)元素，0代表沒(méi)有。 判斷元素是否存在： 加入元素： 刪除元素： 改變?cè)貭顟B(tài)： （如果存在則刪除，否則加入） 與其他集合的交并異或 集合的補(bǔ)： 與其他集合的差： 集合操作 枚舉子集 std:bitset std:bitset用例 自己實(shí)現(xiàn)bitset 內(nèi)部為unsigned int數(shù)組。 與或非異或：對(duì)所有數(shù)字進(jìn)行位運(yùn)算 左移右移： 自己實(shí)現(xiàn)bitset bitset的簡(jiǎn)單應(yīng)用 狀態(tài)壓縮動(dòng)態(tài)規(guī)劃（通常用單個(gè)int表示狀態(tài)，偶爾用得到ll）。 存儲(chǔ)值為bool類型的動(dòng)態(tài)規(guī)劃，如判斷背包是否可行。 以0-1背包為例： 終 THE END 快速冪 枚舉因子 篩法 篩法 進(jìn)一步了解 常用公式 bits