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

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

2、精度加減乘法高精度除法高精度GCD線性同余方程拓展歐幾里得算法拓展歐幾里得算法拓展歐幾里得算法拓展歐幾里得算法：代碼求解線性同余方程分解質(zhì)因數(shù)枚舉因子篩法篩法基礎(chǔ)數(shù)論：例題BASIC NUMBER THEORY: EXAMPLESNOIP2012 D2T1同余方程題面題解 拓展歐幾里得的直接應(yīng)用。 也可以直接算逆元。POJ1061青蛙的約會(huì)題面題解HDU2824The Euler Function題意題解POJ2480Longges Problem題意題解SGU106The Equation題意題解進(jìn)一步了解組合數(shù)學(xué)入門(mén)INTRODUCTORY COMBINATORICS基本計(jì)數(shù)原理加法原理乘

3、法原理減法原理計(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é)入門(mén)：例題INTRODUCTORY COMBINATORICS: EXAMPLES一道數(shù)學(xué)題題面題解POJ3421X-factor Chains題意題解URAL1860Fiborial題面題解POJ3088Push Button Lo

4、ck題面題解無(wú)名試題1題面題解組合數(shù)學(xué)習(xí)題8.5題面題解SKI題面題解進(jìn)一步了解位運(yùn)算與bitsetBITWISE OPERATIONS AND STD:BITSET位運(yùn)算集合的二進(jìn)制表示 適用于全集大小比較?。ㄍǔＴ?2以?xún)?nèi)）的情況。 用一個(gè)unsigned int表示一個(gè)子集。 二進(jìn)制位為1代表子集中有這個(gè)元素，0代表沒(méi)有。判斷元素是否存在：加入元素：刪除元素：改變?cè)貭顟B(tài)：（如果存在則刪除，否則加入）與其他集合的交并異或集合的補(bǔ)：與其他集合的差：集合操作枚舉子集std:bitsetstd:bitset用例自己實(shí)現(xiàn)bitset 內(nèi)部為unsigned int數(shù)組。 與或非異或：對(duì)所有數(shù)字進(jìn)行位運(yùn)算 左移右移：自己實(shí)現(xiàn)bitsetbitset的簡(jiǎn)單應(yīng)用 狀態(tài)壓縮動(dòng)態(tài)規(guī)劃（通常