離散數(shù)學(xué)在信息學(xué)競賽中的運用

1、離散數(shù)學(xué)在信息學(xué)競賽中的運用,Yellow Vigorous Pine,目錄,重集全排列Catalan數(shù)簡單數(shù)論矩陣的簡單運用棋盤多項式與任務(wù)分配置換群與pólya定理,重集全排列,一般我們認(rèn)為排列或組合的元素必須兩兩相異，現(xiàn)取消這一限制。例如一個排列可以是aaaaabbbbbaaaabbbb等等，一個組合可以只{a，a，b，b}。對于重集S＝{p1a1,p2a2……pkak}，其中pi表示ai在集合中的個數(shù)。那么這

2、個重集的全排列個數(shù)是(∑Pi)!/∏(Pi!)，其中(i=1 to k)。,字符串序號,字符串 acab 含有兩個 a ,一個 b ,一個 c ,和 acab 含的字母和每個字母的個數(shù)都相等的字符串還有：aacb,baca等，因為他們也是含有兩個 a ,一個 b ,一個 c 。所有滿足這個性質(zhì)的字符串按字典順序排列后，acab 是第 5 個，我們就說 acab 的序號是 5 .再如：ba 的序號是 2,aa 的序號是 1.編程求出給定字

3、符串 S（長度<=100） 的序號 P（保證<=30000）注意：字符串只含小寫字母。本題可以逐位利用重集全排列的公式，計算出解。,飛行問題,在n×m×k一只飛蛾從空間上的(0,0,0)點飛到(n,m,k)點，規(guī)定飛蛾每次只能向右，向前，向下飛行一單位距離，問飛蛾有多少種不同的路徑可以飛到終點。向右飛行計為a，向前計為b，向下計為c。那么每一個飛行過程就對應(yīng)著一個多個a多個b多個c的排列，反之也對應(yīng)。

4、而a有n個，b有m個，c有k個。所以這些字母全排列的個數(shù)對應(yīng)著飛行路徑的個數(shù)－(m+n+k)!/m!n!k!。,Catalan數(shù),堆棧問題棧有兩種最重要的操作，即pop（從棧頂彈出一個元素）和push（將一個元素進(jìn)棧）?？紤]這樣一個問題：一個操作數(shù)序列，從1，2，一直到n（圖示為1到3的情況），棧A的深度大于n。,Catalan數(shù),現(xiàn)在可以進(jìn)行兩種操作：1.將一個數(shù)，從操作數(shù)序列的頭端移到棧的頭端（對應(yīng)數(shù)據(jù)結(jié)構(gòu)棧的push操作）

5、2. 將一個數(shù)，從棧的頭端移到輸出序列的尾端（對應(yīng)數(shù)據(jù)結(jié)構(gòu)棧的pop操作）使用這兩種操作，由一個操作數(shù)序列就可以得到一系列的輸出序列。例如1 2 3 4 5為初始序列，經(jīng)過進(jìn)棧，出棧，進(jìn)棧，進(jìn)棧，進(jìn)棧，出棧，進(jìn)棧，出棧，出棧操作后，序列變?yōu)榱? 4 5 3 2,Catalan數(shù),試問一個序列1……n經(jīng)過堆棧處理之后，有多少種出棧序列。要知道這個問題如何解決，先將這個問題的模型轉(zhuǎn)換一下。進(jìn)棧時，我們在紙上畫一個左括號，出棧時，畫一個

6、右括號。這樣就把整個進(jìn)棧出棧的過程轉(zhuǎn)化成了一個括號序列。而且任何一個進(jìn)棧出棧的過程都對應(yīng)著唯一的括號序列。,Catalan數(shù),好括號列的定義：（1）空列是好括號列。（2）若A和B是好括號列，則AB是好括號列。（3）若A是好括號列，（A）是好括號列。由好括號的定義可知，任何一個進(jìn)棧出棧過程轉(zhuǎn)化成的括號序列都是好括號列。那么任何一個好括號列也對應(yīng)著一個唯一的進(jìn)棧出棧過程。計算出長度為n（n為完整括號個數(shù)，一個左括號加上一個右括號算作一個完

7、整括號）的好括號列的個數(shù)也就是計算出了堆棧問題的答案。經(jīng)過數(shù)學(xué)證明，長度為n的好括號列的個數(shù)是C（n）＝C(2n,n)-C(2n,n-1)=C(2n,n)/(n+1)。這個數(shù)被稱為Catalan數(shù)(卡特蘭數(shù))。,Catalan數(shù),考慮新X1×X2×X3……×Xn，對這個乘式加括號搞結(jié)合律，則共加n-1個括號，那么添加括號的方案數(shù)是C(n－1)種。若最后一次乘法是(X1,X2……Xk)×(Xk+1

8、,Xk+2……Xn)，那么組合方式也是相乘的(乘法原理)，設(shè)前k個元素的填括號方式有a(k)種，后面的n-k個元素有a(n－k)種，則a(n)=∑a(k)×a(n-k)，其中k＝1 to n-1，a1=1。這就是Catalan數(shù)的遞推公式。由上述的遞推公式可以知道，包含n個結(jié)點的二叉樹有C(n)棵。,小結(jié),可以運用Catalan數(shù)的地方：設(shè)圓周上2n個點，用n條彼此在圓內(nèi)部無公共交點的弦連接這些點，共有C（n）種連接方式。

9、在n×n的矩陣中，從(0,0)點走到(n,n)點，規(guī)定只能向下或向右走，且不能穿過左上到右下的對角線，共有C(n)種走的方式。填括號問題進(jìn)棧出棧問題結(jié)點數(shù)是n的二叉樹的個數(shù),數(shù)論,這里簡要介紹一些實用的數(shù)論算法。求最大公約數(shù)(歐幾里德算法)Function gcd(a,b:longint):longint;Begin if a mod b=0 then gcd:=b

10、 else gcd:=gcd(b,a mod b); End;這里，調(diào)用gcd(a,b)函數(shù)可以求出a和b 的最大公約數(shù)。,歐幾里德算法,狼找兔子一座山周圍有n個洞，順時針編號為0,1,2,…n-1。而一只狼從0號洞開始，順時針方向計數(shù)，每遇到m個洞就進(jìn)洞找兔子。例如n=5，m=3，狼經(jīng)過的洞依次為0,3,1,4,2,0。輸入n和m。試問兔子有沒有幸免的機(jī)會，如果有，該藏在哪兒？,狼找兔子,不妨讓兔子躲在1號洞，因為若狼能從0號

11、洞到達(dá)1號洞，則必能從1號洞到達(dá)2號洞，……，兔子難逃厄運。反過來說，若有安全洞，則1號洞就是其中一個。再來看狼的運動。狼的第i次運動后的洞址應(yīng)該是(m×i) mod n。若(m×i) mod n=1，即狼第i次運動后到達(dá)1號洞，則gcd(m,n)=1。因為若gcd(m,n)=k>1，則由(m’×k×i) mod (n’×k)=1，設(shè)m’×k=m，n’×k=n

12、，m’×k×i-[(m’×k×i) / (n’×k)] × n’×k=1。得出1/k是整數(shù)，與k>1矛盾。所以當(dāng)gcd(n,m)=1時，兔子無法幸免。反之，兔子應(yīng)該選擇除了{(lán)i×gcd(m,n)|i=0…(n/gcd(m,n)-1)}外的洞躲藏。,擴(kuò)展歐幾里德算法,下面，我們對歐幾里德算法進(jìn)行推廣，使得該算法不僅能得出任意兩個正整數(shù)a和b的最大公約數(shù)d

13、，而且還能計算出滿足下式的整系數(shù)x和y。D=gcd(a,b)=ax+by(x和y可能為0或負(fù)數(shù)),擴(kuò)展歐幾里德,Function euclid(a,b:longint; var x,y:longint):longint;Var t:longint;Begin if b=0 then begin euclid:=a; x:=1; y:=0; endElse begin euclid:=euclid(

14、b,a mod b,x,y); t:=x; x:=y; y:=t-(a div b)*y; end;End;,擴(kuò)展歐幾里德算法,上述函數(shù)是從歐幾里德算法中衍生出來的。算法一開始，它首先測試b=0，若b=0，返回當(dāng)前最大公約數(shù)a，x=1，y=0，以使a=gcd(a,0)=a*1+b*0；若b0，則歐幾里德算法首先計算出d’=gcd(b,a mod b) = bx’+(a mod b)*y’中的x’和y’。在這種情況下，d=g

15、cd(a,b)=d’=gcd(b,a mod b)。為了得到d=ax+by的x和y，我們利用等式d=d’=bx’+(a mod b)y’得出d=bx’+(a-(a div b)b)y’=ay’+b(x’-(a div b)y’)。因此，x=y’; y:=x’-(a div b)*y’。,解的個數(shù),已知x,y滿足如下條件：ax+by+c=0 ; x1<=x ; x<=x2 ; y1<=y ; y<=y2 ; x,

16、y均為整數(shù)。其中：a,b,c,x1,x2,y1,y2都是絕對值不超過10^8的整數(shù)。求(x,y)的解的個數(shù)。輸入：a,b,c,x1,x2,y1,y2輸出：輸出解的個數(shù)樣例輸入1 1 1 -10 10 -9 9樣例輸出19,解的個數(shù),直接的枚舉顯然是不符合時間要求的。由于方程所有解之間的關(guān)系是可以互相推導(dǎo)的，所以如果我們已知了方程的一個解，那么用數(shù)學(xué)方法推導(dǎo)出其他的解，繼而統(tǒng)計解的個數(shù)。所以在求解方程的任意一個解的時候，

17、我們可以用到擴(kuò)展的歐幾里德算法。,素數(shù)的測試,剛剛接觸信息學(xué)的時候，可能就做過關(guān)于素數(shù)測試的題目，當(dāng)時的方法是2-sqrt(n)的枚舉，這樣的效率并不高。歐拉定理：aψ(n) ≡1(mod n)，其中ψ(n) 是n的歐拉函數(shù)，ψ(n) ＝不大于n的但與n互質(zhì)的正整數(shù)個數(shù)。a可以取任意值。易知，ψ(素數(shù)n)=n-1,費爾馬小定理,從而，當(dāng)n是質(zhì)數(shù)的時候，an－1 ≡1(mod n)，這是歐拉定理的特殊情況，也稱為費爾馬小定理。那么，

18、費爾馬小定理的逆定理是否成立呢？答案是否定的，但是這種情況很少。也就是說，對于a取1－n-1的任意一個值的時候，都有an－1 ≡1(mod n)成立的話，則幾乎可以可定地確認(rèn)n是素數(shù)。,費爾馬小定理,當(dāng)a=2時，小于104的n值中，只會產(chǎn)生22個不成立的n。當(dāng)a＝3時，在小于108地n值中，只會產(chǎn)生255個不成立的n。顯然可以看出這個出錯的概率是很小的。我們用分治法，可以在klogN的復(fù)雜度內(nèi)判斷N是否為素數(shù)。其中k是a的取值次數(shù)。

19、一般情況下，我們只需要讓a=2,3,4判斷一下就可以了。于是費爾馬小定理的逆定理成為了我們進(jìn)行素數(shù)測試的有效算法之一。,選數(shù),選數(shù)(Noip2002普及組) 已知n個整數(shù)x1,x2,…,xn，以及一個整數(shù)k(k<n)。從n個整數(shù)中任選k個整數(shù)相加，可分別得到一系列的和。例如當(dāng)n=4,k=3，4個整數(shù)分別為3，7，12，19時，可得全部的組合與它們的和為：3+7+12=22 3+7+19=29 7+12+19=38

20、3+12+19=34,選數(shù),現(xiàn)在，要求你計算出和為素數(shù)共有多少種。輸入格式為：n,k (1≤n≤20，k<n)x1,x2,…xn (1≤xi≤5000000)一個整數(shù)(滿足條件的種數(shù))。樣例輸入：4 33 7 12 19樣例輸出：1,選數(shù),這一題采取的是搜索的算法，這已經(jīng)是十分低效的了，但是還得加上素數(shù)判定的復(fù)雜度，所以這里采取費爾馬小定理的逆定理判定素數(shù)才能使得整個程序在短時間內(nèi)出解。,小結(jié),關(guān)于數(shù)論的一些知識本

21、人還十分缺陷，所以只能做一些簡單知識的介紹。,矩陣的簡單運用－by 韓文弢,由m行、n列的標(biāo)量所構(gòu)成的數(shù)組被稱為一個m×n的矩陣(matrix)。一般用大寫字母表示矩陣，對應(yīng)的小寫字母表示矩陣中的項(entry)。這里，aij就是矩陣A中第i行第j列的項。,矩陣的乘法,設(shè)A=(aij)m×n,B=(bij)n×p是兩個矩陣，矩陣C=AB，則C是一個m×p的矩陣，且其中第i行第j列的項的值為A中

22、第i個行向量與B中第j個列向量的內(nèi)積。也就是說，,矩陣乘法舉例,矩陣乘法的應(yīng)用,求無權(quán)圖中長度為k的路徑數(shù),矩陣乘法運算的性質(zhì),不滿足交換律AB=BA不一定成立滿足結(jié)合律(AB)C=A(BC)成立滿足分配律A(B+C)=AB+AC成立（左分配律）(A+B)C=AC+BC成立（右分配律）,例題1：遞推數(shù)列(recurrence),1≤k≤100，0≤n≤1,000,000,例題1樣例,輸入樣例2 101 11 1輸出

23、樣例89,遞推數(shù)列解答,Fibonacci數(shù)列遞推公式：fi=fi-1+fi-2另外再設(shè)一個矩陣A，使得容易看出，即，,遞推數(shù)列解答（續(xù)）,設(shè)則有如何降低復(fù)雜度？時間復(fù)雜度：O(logn),分治！,遞推數(shù)列解答（續(xù)）,推廣到一般情況，其中，時間復(fù)雜度：O(k3logn),例題2：圖形變換(shape),1≤n≤10,000，1≤m≤10,000,例題2樣例,輸入樣例4 1M 0 1Z 0.5R 45F 0

24、2 1輸出樣例0.0000 -1.4142,圖形變換解答,直觀算法：直接模擬時間復(fù)雜度：O(mn)太慢了！改進(jìn)算法：矩陣運算時間復(fù)雜度：O(m+n)很好！實際應(yīng)用三維圖形處理,小結(jié),線性代數(shù)是一件十分有力的數(shù)學(xué)工具。一般地，矩陣乘法可以用來解決大量線性關(guān)系的計算，能夠把問題大大簡化。 而線性方程組則是解決自然科學(xué)問題的常用工具，可以用矩陣的基本操作來求解。 涉及思想：分治思想轉(zhuǎn)化思想消元思想,棋盤多項式和

25、任務(wù)分配,任務(wù)分配有N位工作人員，同時有N項任務(wù)，每人必須承擔(dān)一項任務(wù)，若給出某人不能從事的某些任務(wù)，問要安排好工作，共有多少種方案？N<=100，所有人員不能從事的任務(wù)之和不大于20。,棋盤多項式和任務(wù)分配,先來了解一下錯排問題。如下圖所示，每個元素不能對應(yīng)自己，由容斥原理，所有的排列方法有n!(1-1/1!+1/2!-1/3!…..+((-1)n)*1/n!),1 2 3 4,2 1 4 3,棋盤多項式和任務(wù)分配,其實這

26、也是一個任務(wù)分配問題，相當(dāng)于1號工作人員不能做1號工作，2號工作人員不能做2號工作…以次類推。可是現(xiàn)在的情況變得一般化了。那么應(yīng)該怎樣來解決這個問題呢？,容斥原理！,棋盤多項式和任務(wù)分配,可以列出一個N*N的棋盤，如果i號工作人員不能從事j號工作，那么在i,j處的格子上圖紅。如錯排問題的棋盤表示則是：,棋盤多項式和任務(wù)分配,我們稱紅色的區(qū)域為禁區(qū)，紅色的格子為禁位。我們的任務(wù)就是把N個棋子放到棋盤中不是禁區(qū)的地方，且使得每一行和每一列

27、只有一顆棋子。我們這種排列叫做有限制排列（或者是禁位全排列）,棋盤多項式和任務(wù)分配,如果我們知道了將k科棋子放入禁區(qū)的所有放法rk(C),其中C表示棋盤。那么，由容斥原理，整個禁位排列的數(shù)目為：,Qn=n!-(n-1)!r1+(n-2)!r2-...+((-1)^n)0!rn,棋盤多項式和任務(wù)分配,下面的問題變成了如何求rk?對于任何一張棋盤(以后所指的棋盤都是指原棋盤上的禁區(qū)部分)，r0(C)=1.構(gòu)造棋盤多項式R(C)=r0(C)x

28、0+r1(C)x1…rk(C)xk.如果我們知道了一張棋盤的棋盤多項式，那么就知道了任意一個rk。由上式可知，R(Ф)=1。,棋盤多項式和任務(wù)分配,那么如何求得任意一塊棋盤的棋盤多項式呢？我們可以試著找找遞推公式！不難發(fā)現(xiàn)，k枚棋子對棋盤C進(jìn)行布局的方案，可按選定格子放子與不放子劃分為兩類：對選定的格子放一枚棋子,有rk－1(Ci)種。 Ci表示去掉該個選定格子所在行和列后剩下的棋盤。對選定的格子不放棋子，有rk(Ce)種,

29、Ce表示去掉該個選定的格子以后的棋盤。,棋盤多項式和任務(wù)分配,由加法原理可以知道 rk(C)=rk－1(Ci)＋rk(Ce)于是我們利用上面上面的式子對棋盤多項式R(C)進(jìn)行推導(dǎo)。R(C)= ∑ rk(C) xk ＝∑[rk－1(Ci)+ rk(Ce)]xk = x ∑ rk(Ci)xk + ∑ rk(Ce)xk 　

30、　　　　　　 ＝xR(Ci) + R(C e),k=0,n,n,n,n,k=0,k=0,k=0,棋盤多項式和任務(wù)分配,R( )=1+ x；,,,R( )= x R( ) + R( ) = x(1 + x )+1 + x =1+ 2x +x2,,,,,R( )= xR( )+ R(

31、)= 1+2x；,,,R( ) = xR( ) + R( ) = 1+6x +10 x2 +4x3,,,,,,,,,,,,,,,棋盤多項式和任務(wù)分配,把整個棋盤作為參數(shù)傳遞，可以遞推出整個棋盤的棋盤多項式。這里當(dāng)然需要加入一些多項式乘法和加法的東西。具體分析整個程序的復(fù)雜度，可以發(fā)現(xiàn)是跟禁區(qū)的格子數(shù)目有著跟大的關(guān)系！如果直接這樣做的話，復(fù)雜度是220

32、5;多項式運算的復(fù)雜度。由于是整個數(shù)組作為參數(shù)在傳遞，所以這個在時間和空間上都是不理想的。實際測試的時候會有一個點超時。,棋盤多項式和任務(wù)分配,分治！,怎么辦,棋盤多項式和任務(wù)分配,先定義兩個名稱：獨立格和獨立塊。獨立格：兩個既不在同一行也不在同一列的格子。獨立塊：兩個塊中的所有格子分別都是獨立格。顯然一個獨立塊也是有他的多項式的，而對于兩個獨立塊，他們放棋子的時候是不會互相影響的？！,棋盤多項式和任務(wù)分配,如圖所示，紅色和綠色是

33、兩個對應(yīng)的獨立塊。,棋盤多項式和任務(wù)分配,可以把剛才的棋盤分成兩塊：,,分別對這兩塊棋盤遞推出他們的多項式R(C1)和 R(C2),棋盤多項式和任務(wù)分配,因為這兩塊是相對獨立的，所以依據(jù)乘法原理，整個棋盤的多項式是：,R(C)=R(C1)×R(C2),棋盤多項式和任務(wù)分配,舉一個簡單的例子來說明分治以后的復(fù)雜度情況。上圖原本的復(fù)雜度是25,分治以后的復(fù)雜度降為了5×21.也就是說，如果在禁區(qū)格子數(shù)為20的情況下，若

34、是能分成兩塊格子數(shù)為10的獨立塊，那么復(fù)雜度由220降為了2×210.,棋盤多項式和任務(wù)分配,在實際測試的時候，可以發(fā)現(xiàn)按上述方法做的程序雖然能運行出答案，但是會出現(xiàn)空間消耗太多錯誤提示，這是不夠理想的。,我們把棋盤當(dāng)作參數(shù)在傳遞！,棋盤多項式和任務(wù)分配,怎么處理這個問題呢？,從題目的一些特殊條件入手！,棋盤多項式和任務(wù)分配,題目中有這樣的一句話：所有人員不能從事的任務(wù)之和不大于20。我們處理的只是棋盤的禁區(qū)而已，所以在傳

35、遞參數(shù)的時候不用傳遞整張棋盤，傳遞每個禁格的位置就行了?？臻g的占用量似乎是下降了2500倍?。?！,不錯！,棋盤多項式和任務(wù)分配,運行結(jié)果的比較：,小結(jié),棋盤多項式在信息學(xué)競賽中的運用不是很廣泛，似乎只能解決任務(wù)分配一類的問題。這里做一個了解即可。,置換群與pólya定理,先看一個例題：有n個人，按1－n編號。每個人手里都拿著一個球，這些球也按1－n編號。但是1號選手手里拿的不一定是1號球，所以他們可以兩兩相互交換手里的球，使

36、得最終i號選手手里的是i號球。請問如果交換可以同時進(jìn)行，那么最少需要多少個單位時間（兩兩交換一次是一個單位時間），最少又需要多少次交換？,置換群,在解決這個問題之前，需要先學(xué)習(xí)一些群論，特別是置換群的知識。這里只介紹一些結(jié)論。將每個人編號和所拿的球的編號一一對應(yīng)起來寫成如下形式：這稱為一個置換群。如果把i和j下面的元素交換，稱為一次置換。,置換群,例如 (1 2 3 4) (3 4 1 2)這是一個置換群。

37、下面進(jìn)行一種操作，在第一行中找到1，然后看1下面的元素，是3，然后在第一行中找3，3下面的元素是1。這樣我們找出了1－3找個循環(huán)節(jié)，寫成：(1 3) (3 1)然后找2，2下面的元素是 4，接著4下面的元素又是2，所以又找出了一個循環(huán)節(jié)(2 4)

38、 (4 2),置換群,在這里，1－3的循環(huán)節(jié)和2－4的循環(huán)節(jié)被成為輪換。一個置換群可以寫成若干個輪換的乘積：(1 2 3 4)＝(1 3)×(2 4)(3 4 1 2) (3 1) (4 2)再來看看題目，根據(jù)題目給出的信息，可以構(gòu)造出一個置換群，在該置換群中，可以分解出若干個輪換。試想如果交換在不同的輪換內(nèi)進(jìn)行，也就是輪換1中的元素和輪換2中的元素交換。這樣必定不會達(dá)到最優(yōu)的交換次數(shù)（為

39、什么？）。所以對于每一個輪換，我們可以分別進(jìn)行處理。,置換群,由于每個輪換都是一個循環(huán)，他們的本質(zhì)是相同的，也就是我們可以對輪換中的元素進(jìn)行重新的編號。于是一個長度為n的輪換可以寫成如下形式：(1 2 3 ……n-1 n)(2 3 4 …… n 1)問題現(xiàn)在已經(jīng)一般化了，長度為n的輪換，最少需要多少個單位時間的交換和最少需要交換幾次呢？當(dāng)n確定時，答案是肯定的。,置換群,結(jié)論1：任何一個輪換的，使得所有元素歸位的交換次數(shù)最少為

40、n-1。利用輪換中的任意一個元素和剩下的元素進(jìn)行交換，可以使得所有元素歸位，且交換次數(shù)最少。結(jié)論2：交換可以同時進(jìn)行時，最多需要兩個單位的交換時間。做如下操作，將1和n下面的元素交換，2和n-1下面的元素交換……這樣的交換可以在1個單位時間內(nèi)進(jìn)行，完成這次操作后，將2和n下面的元素交換，3和n-1下面的元素交換……這也只需要一個單位的交換時間。進(jìn)行了上述操作后，可以驚奇地發(fā)現(xiàn)，所有的元素都已經(jīng)歸位了！交換次數(shù)是n-1次，這是最少的交換

41、次數(shù)。當(dāng)然當(dāng)n＝1時，無需交換時間；n＝2時只要1個單位的交換時間，其他任何情況都只需要2個單位的交換時間就可以了。,書架,書架書架上有n本書，順序被打亂了。每次可以交換兩本編號奇偶性不同的書。要求用最少的步驟，使所有書歸位。N<=1000。,書架,例如有4本書，最初，書架上從左到右的書的編號依次是(2, 4, 1, 3)，我們可以先交換(1, 2)得到(1, 4, 2, 3)，再交換(3, 4)得到(1, 3, 2, 4)，最

42、后交換(3, 2)得到(1, 2, 3, 4)題目似乎多了一個條件，就是需要奇位和偶位交換。其實道理還是一樣的。在一個輪換中，如果奇位和偶位的元素都存在，可以利用任意一個奇位將偶位元素置換到位，也可以利用任意一個偶位將奇數(shù)元素置換到位，置換次數(shù)還是輪換長度-1。,書架,當(dāng)輪換中只有奇位元素或者只有偶位元素的時候，這時，需要借助該輪換外的其他元素進(jìn)行交換了。如果輪換中都是奇位，可以先將輪換中的某個元素和輪換外的一個偶位元素交換，然后利用

43、偶位元素，把所有元素都置換歸位。最后再和原來的那個奇位元素進(jìn)行一次置換，這樣，原來的那個奇位元素也歸位了。這就是借助輪換外的元素進(jìn)行交換操作。可以證明，這樣的操作能夠使得交換次數(shù)最少。,無聊的排序,無聊的排序給出n個各不相同的數(shù)，每次操作是交換兩個數(shù)，代價是這兩個數(shù)的和。請你用最少的代價，使得所有元素從小到大排列。例如(8 4 5 3 2 7)=>(8 4 5 3 7 2)=>(2 4 5 3 7 8)=>(2 4

44、 3 5 7 8)=>(2 3 4 5 7 8)。這樣的交換可以使得代價值之和最小。,無聊的排序,仍然考慮輪換的問題。在一個輪換中，利用任意一個元素和其他元素交換，可以使得所有元素歸位。那么我們選取輪換中最小的那個元素，然后和別的元素進(jìn)行交換，這樣可以使得交換的代價值之和“最小”。但是這個代價值一定最小的嗎？為什么要只能在輪換內(nèi)進(jìn)行交換呢？會不會和輪換外的元素交換之后，能使代價值更小呢？答案是肯定的！可以利用輪換外的元素。,無

45、聊的排序,舉個例子：(1 8 9 7 6)，輪換為(1)(8 9 7 6)。目標(biāo)狀態(tài)是(1 6 7 8 9)，先把輪換外最小元素1和輪換中最小元素6交換=>(6 8 9 7 1)，然后利用1使得輪換中所有元素歸位=>(6 8 1 7 9)=>(6 8 7 1 9)=>(6 1 7 8 9)，最后再把1交換出去=>(1 6 7 8 9)。這樣的操作可以使得代價值更加小。所以在對一個輪換進(jìn)行處理的時候，應(yīng)該考

46、慮兩種交換方式，選擇更優(yōu)秀的交換方式進(jìn)行。,pólya定理,pólya定理是用來解決一般染色問題的有效方法。例如給出一個三角形，要求你對三角形的邊和點進(jìn)行染色，有m種顏色可以供你選擇，每條邊和每個點必須染色。問你經(jīng)過翻轉(zhuǎn)旋轉(zhuǎn)等操作后，仍然本質(zhì)不同的三角形個數(shù)有多少種。,pólya定理,對頂點和邊進(jìn)行標(biāo)號，例如一個正三角形可以這樣標(biāo)號：把本質(zhì)不用的旋轉(zhuǎn)翻轉(zhuǎn)操作，用置換群表示。例如向右旋轉(zhuǎn)60o的操作

47、可以表示成(1 2 3 4 5 6)(3 1 2 6 4 5)表示1的地方被3代替，2的地方被1代替。,pólya定理,假設(shè)可以列出k個置換群，且在第i個置換群中輪換的個數(shù)為fi，偉大的數(shù)學(xué)家pólya研究出了一個讓人興奮的結(jié)論：用m種顏色對圖形進(jìn)行染色，本質(zhì)不同的染色方案數(shù)為(mf1+mf2…+mfk)/k。這是一個偉大的結(jié)論，對于信息學(xué)競賽來說，只需要記住這個結(jié)論即可。,pólya定理,黑白瓷磚

48、小可可在課余的時候受美術(shù)老師的委派從事一項漆繪瓷磚的任務(wù)。首先把(n+1)×n/2塊正六邊形瓷磚拼成三角形的形狀下圖給出了n=3時拼成的“瓷磚三角形”。然后把每一塊瓷磚漆成純白色或者純黑色，而且每塊瓷磚的正、反兩面都必須漆成同樣的顏色。有一天小可可突發(fā)奇想，覺得有必要試試看這些瓷磚究竟能漆成多少種本質(zhì)不用的圖案。所謂兩種圖案本質(zhì)不同就是其中的一種圖案無論如何旋轉(zhuǎn)、或者翻轉(zhuǎn)、或者同時旋轉(zhuǎn)和翻轉(zhuǎn)都不能得到另外一種圖案。,p&#

49、243;lya定理,旋轉(zhuǎn)是將瓷磚三角形整體順時針旋轉(zhuǎn)120o或240o。,pólya定理,翻轉(zhuǎn)是將瓷磚三角形整體左右翻轉(zhuǎn)180o。,pólya定理,一開始，小可可覺得這項實驗很有意思，他知道n=1時有兩種不同的漆繪方案，n=2時也只有4種不同的漆繪方案，小可可還把這些方案畫了出來。,pólya定理,但是后來小可可發(fā)現(xiàn)n在變大的過程中，漆繪方案增長的速度很快，在n=14的時候，居然有6760803201217

50、259503457555972096種不同的漆繪方案。這果然是一項非常艱巨的實驗。因此他決定請你編寫程序幫他求解本質(zhì)不同的漆繪方案數(shù)s。,pólya定理,這一題顯然可以直接套用pólya定理。首先需要做一件比較麻煩的事情，就是找出每一個置換群。題目給出的信息告訴我們，所有的重復(fù)方案都是由旋轉(zhuǎn)和翻轉(zhuǎn)的組合得到的。這里定義兩個過程，一個是左右翻轉(zhuǎn)，一個是順時針旋轉(zhuǎn)120o。這樣調(diào)用這兩個過程可以得出所有的重復(fù)方案。共6

51、種。,pólya定理,Procedure turn(Var a:SetType);//旋轉(zhuǎn)var i,j:integer; tmp:SetType;begin tmp:=a; for i:=1 to n do for j:=1 to i do a[i,j]:=tmp[n-j+1,i-j+1];end;,pólya定理,Procedure turnover(Var a:SetType);//

52、翻轉(zhuǎn)var i,j:integer; tmp:SetType;begin tmp:=a; for i:=1 to n do for j:=1 to i do a[i,j]:=tmp[i,i-j+1];end;,pólya定理,剩下的任務(wù)只要知道pólya定理就可以容易地解決。用DFS求出沒個置換群中的輪換個數(shù)，然后進(jìn)行高精度運算。,小結(jié),置換群和pólya定理在信息學(xué)競賽中的運