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

1、離散數(shù)學在信息學競賽中的運用Yellow Vigorous Pine1目錄重集全排列Catalan數(shù)簡單數(shù)論矩陣的簡單運用棋盤多項式與任務分配置換群與plya定理2重集全排列一般我們認為排列或組合的元素必須兩兩相異，現(xiàn)取消這一限制。例如一個排列可以是aaaaabbbbbaaaabbbb等等，一個組合可以只a，a，b，b。對于重集Sp1a1,p2a2pkak，其中pi表示ai在集合中的個數(shù)。那么這個重集的全排列個數(shù)是(Pi)!/(Pi!)，其中(i=1 to k)。 3字符串序號字符串 acab 含有兩個 a ,一個 b ,一個 c ,和 acab 含的字母和每個字母的個數(shù)都相等的字符串還有：a

2、acb,baca等，因為他們也是含有兩個 a ,一個 b ,一個 c 。所有滿足這個性質的字符串按字典順序排列后，acab 是第 5 個，我們就說 acab 的序號是 5 .再如：ba 的序號是 2,aa 的序號是 1.編程求出給定字符串 S（長度=100） 的序號 P（保證1，則由(mki) mod (nk)=1，設mk=m，nk=n，mki-(mki) / (nk) nk=1。得出1/k是整數(shù)，與k1矛盾。所以當gcd(n,m)=1時，兔子無法幸免。反之，兔子應該選擇除了igcd(m,n)|i=0(n/gcd(m,n)-1)外的洞躲藏。14擴展歐幾里德算法下面，我們對歐幾里德算法進行推廣，

3、使得該算法不僅能得出任意兩個正整數(shù)a和b的最大公約數(shù)d，而且還能計算出滿足下式的整系數(shù)x和y。D=gcd(a,b)=ax+by(x和y可能為0或負數(shù))15擴展歐幾里德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(b,a mod b,x,y); t:=x; x:=y; y:=t-(a div b)*y; end;End;16擴展歐幾里德算法上述函數(shù)是從歐幾里

4、德算法中衍生出來的。算法一開始，它首先測試b=0，若b=0，返回當前最大公約數(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=gcd(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。17解的個數(shù)已知x,y滿足如下條件：ax+by+c=0 ; x1=x

5、 ; x=x2 ; y1=y ; y=y2 ; x,y均為整數(shù)。其中：a,b,c,x1,x2,y1,y2都是絕對值不超過108的整數(shù)。求(x,y)的解的個數(shù)。輸入：a,b,c,x1,x2,y1,y2輸出：輸出解的個數(shù)樣例輸入1 1 1 -10 10 -9 9樣例輸出1918解的個數(shù)直接的枚舉顯然是不符合時間要求的。由于方程所有解之間的關系是可以互相推導的，所以如果我們已知了方程的一個解，那么用數(shù)學方法推導出其他的解，繼而統(tǒng)計解的個數(shù)。所以在求解方程的任意一個解的時候，我們可以用到擴展的歐幾里德算法。19素數(shù)的測試剛剛接觸信息學的時候，可能就做過關于素數(shù)測試的題目，當時的方法是2-sqrt(n)

6、的枚舉，這樣的效率并不高。歐拉定理：a(n) 1(mod n)，其中(n) 是n的歐拉函數(shù)，(n) 不大于n的但與n互質的正整數(shù)個數(shù)。a可以取任意值。易知，(素數(shù)n)=n-1 20費爾馬小定理從而，當n是質數(shù)的時候，an1 1(mod n)，這是歐拉定理的特殊情況，也稱為費爾馬小定理。那么，費爾馬小定理的逆定理是否成立呢？答案是否定的，但是這種情況很少。也就是說，對于a取1n-1的任意一個值的時候，都有an1 1(mod n)成立的話，則幾乎可以可定地確認n是素數(shù)。21費爾馬小定理當a=2時，小于104的n值中，只會產生22個不成立的n。當a3時，在小于108地n值中，只會產生255個不成立的

7、n。顯然可以看出這個出錯的概率是很小的。我們用分治法，可以在klogN的復雜度內判斷N是否為素數(shù)。其中k是a的取值次數(shù)。一般情況下，我們只需要讓a=2,3,4判斷一下就可以了。于是費爾馬小定理的逆定理成為了我們進行素數(shù)測試的有效算法之一。22選數(shù)選數(shù)(Noip2002普及組) 已知n個整數(shù)x1,x2,xn，以及一個整數(shù)k(kn)。從n個整數(shù)中任選k個整數(shù)相加，可分別得到一系列的和。例如當n=4,k=3，4個整數(shù)分別為3，7，12，19時，可得全部的組合與它們的和為：3+7+12=22 3+7+19=29 7+12+19=38 3+12+19=3423選數(shù)現(xiàn)在，要求你計算出和為素數(shù)共有多少種。輸

8、入格式為：n,k (1n20，kn)x1,x2,xn (1xi5000000)一個整數(shù)(滿足條件的種數(shù))。樣例輸入：4 33 7 12 19樣例輸出：124選數(shù)這一題采取的是搜索的算法，這已經是十分低效的了，但是還得加上素數(shù)判定的復雜度，所以這里采取費爾馬小定理的逆定理判定素數(shù)才能使得整個程序在短時間內出解。25小結關于數(shù)論的一些知識本人還十分缺陷，所以只能做一些簡單知識的介紹。26矩陣的簡單運用by 韓文弢由m行、n列的標量所構成的數(shù)組被稱為一個mn的矩陣(matrix)。一般用大寫字母表示矩陣，對應的小寫字母表示矩陣中的項(entry)。這里，aij就是矩陣A中第i行第j列的項。27矩陣的

9、乘法設A=(aij)mn,B=(bij)np是兩個矩陣，矩陣C=AB，則C是一個mp的矩陣，且其中第i行第j列的項的值為A中第i個行向量與B中第j個列向量的內積。也就是說，28矩陣乘法舉例29矩陣乘法的應用求無權圖中長度為k的路徑數(shù)1234530矩陣乘法運算的性質不滿足交換律AB=BA不一定成立滿足結合律(AB)C=A(BC)成立滿足分配律A(B+C)=AB+AC成立（左分配律）(A+B)C=AC+BC成立（右分配律）31例題1：遞推數(shù)列(recurrence)1k100，0n1,000,00032例題1樣例輸入樣例2 101 11 1輸出樣例8933遞推數(shù)列解答Fibonacci數(shù)列遞推公式

10、：fi=fi-1+fi-2另外再設一個矩陣A，使得容易看出，即，34遞推數(shù)列解答（續(xù)）設則有如何降低復雜度？時間復雜度：O(logn)分治！35遞推數(shù)列解答（續(xù)）推廣到一般情況，其中，時間復雜度：O(k3logn)36例題2：圖形變換(shape)1n10,000，1m10,00037例題2樣例輸入樣例4 1M 0 1Z 0.5R 45F 02 1輸出樣例0.0000 -1.414238圖形變換解答直觀算法：直接模擬時間復雜度：O(mn)太慢了！改進算法：矩陣運算時間復雜度：O(m+n)很好！實際應用三維圖形處理39小結線性代數(shù)是一件十分有力的數(shù)學工具。一般地，矩陣乘法可以用來解決大量線性關系

11、的計算，能夠把問題大大簡化。 而線性方程組則是解決自然科學問題的常用工具，可以用矩陣的基本操作來求解。 涉及思想：分治思想轉化思想消元思想40棋盤多項式和任務分配任務分配有N位工作人員，同時有N項任務，每人必須承擔一項任務，若給出某人不能從事的某些任務，問要安排好工作，共有多少種方案？N20s很大程序2（分）2s大程序3（參）0.5s小61小結棋盤多項式在信息學競賽中的運用不是很廣泛，似乎只能解決任務分配一類的問題。這里做一個了解即可。62置換群與plya定理先看一個例題：有n個人，按1n編號。每個人手里都拿著一個球，這些球也按1n編號。但是1號選手手里拿的不一定是1號球，所以他們可以兩兩相互

12、交換手里的球，使得最終i號選手手里的是i號球。請問如果交換可以同時進行，那么最少需要多少個單位時間（兩兩交換一次是一個單位時間），最少又需要多少次交換？63置換群在解決這個問題之前，需要先學習一些群論，特別是置換群的知識。這里只介紹一些結論。將每個人編號和所拿的球的編號一一對應起來寫成如下形式：這稱為一個置換群。如果把i和j下面的元素交換，稱為一次置換。64置換群例如 (1 2 3 4) (3 4 1 2)這是一個置換群。下面進行一種操作，在第一行中找到1，然后看1下面的元素，是3，然后在第一行中找3，3下面的元素是1。這樣我們找出了13找個循環(huán)節(jié)，寫成：(1 3) (3 1)然后找2，2下面

13、的元素是 4，接著4下面的元素又是2，所以又找出了一個循環(huán)節(jié)(2 4) (4 2)65置換群在這里，13的循環(huán)節(jié)和24的循環(huán)節(jié)被成為輪換。一個置換群可以寫成若干個輪換的乘積：(1 2 3 4)(1 3)(2 4)(3 4 1 2) (3 1) (4 2)再來看看題目，根據(jù)題目給出的信息，可以構造出一個置換群，在該置換群中，可以分解出若干個輪換。試想如果交換在不同的輪換內進行，也就是輪換1中的元素和輪換2中的元素交換。這樣必定不會達到最優(yōu)的交換次數(shù)（為什么？）。所以對于每一個輪換，我們可以分別進行處理。66置換群由于每個輪換都是一個循環(huán)，他們的本質是相同的，也就是我們可以對輪換中的元素進行重新的

14、編號。于是一個長度為n的輪換可以寫成如下形式：(1 2 3 n-1 n)(2 3 4 n 1)問題現(xiàn)在已經一般化了，長度為n的輪換，最少需要多少個單位時間的交換和最少需要交換幾次呢？當n確定時，答案是肯定的。67置換群結論1：任何一個輪換的，使得所有元素歸位的交換次數(shù)最少為n-1。利用輪換中的任意一個元素和剩下的元素進行交換，可以使得所有元素歸位，且交換次數(shù)最少。結論2：交換可以同時進行時，最多需要兩個單位的交換時間。做如下操作，將1和n下面的元素交換，2和n-1下面的元素交換這樣的交換可以在1個單位時間內進行，完成這次操作后，將2和n下面的元素交換，3和n-1下面的元素交換這也只需要一個單位

15、的交換時間。進行了上述操作后，可以驚奇地發(fā)現(xiàn)，所有的元素都已經歸位了！交換次數(shù)是n-1次，這是最少的交換次數(shù)。當然當n1時，無需交換時間；n2時只要1個單位的交換時間，其他任何情況都只需要2個單位的交換時間就可以了。68書架書架書架上有n本書，順序被打亂了。每次可以交換兩本編號奇偶性不同的書。要求用最少的步驟，使所有書歸位。N(8 4 5 3 7 2)=(2 4 5 3 7 8)=(2 4 3 5 7 8)=(2 3 4 5 7 8)。這樣的交換可以使得代價值之和最小。72無聊的排序仍然考慮輪換的問題。在一個輪換中，利用任意一個元素和其他元素交換，可以使得所有元素歸位。那么我們選取輪換中最小的

16、那個元素，然后和別的元素進行交換，這樣可以使得交換的代價值之和“最小”。但是這個代價值一定最小的嗎？為什么要只能在輪換內進行交換呢？會不會和輪換外的元素交換之后，能使代價值更小呢？答案是肯定的！可以利用輪換外的元素。73無聊的排序舉個例子：(1 8 9 7 6)，輪換為(1)(8 9 7 6)。目標狀態(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)。這樣的操作可以使得代價值更加小。所以在對一個輪換進行

17、處理的時候，應該考慮兩種交換方式，選擇更優(yōu)秀的交換方式進行。74plya定理plya定理是用來解決一般染色問題的有效方法。例如給出一個三角形，要求你對三角形的邊和點進行染色，有m種顏色可以供你選擇，每條邊和每個點必須染色。問你經過翻轉旋轉等操作后，仍然本質不同的三角形個數(shù)有多少種。75plya定理對頂點和邊進行標號，例如一個正三角形可以這樣標號：把本質不用的旋轉翻轉操作，用置換群表示。例如向右旋轉60o的操作可以表示成(1 2 3 4 5 6)(3 1 2 6 4 5)表示1的地方被3代替，2的地方被1代替。76plya定理假設可以列出k個置換群，且在第i個置換群中輪換的個數(shù)為fi，偉大的數(shù)學

18、家plya研究出了一個讓人興奮的結論：用m種顏色對圖形進行染色，本質不同的染色方案數(shù)為(mf1+mf2+mfk)/k。這是一個偉大的結論，對于信息學競賽來說，只需要記住這個結論即可。77plya定理黑白瓷磚小可可在課余的時候受美術老師的委派從事一項漆繪瓷磚的任務。首先把(n+1)n/2塊正六邊形瓷磚拼成三角形的形狀下圖給出了n=3時拼成的“瓷磚三角形”。然后把每一塊瓷磚漆成純白色或者純黑色，而且每塊瓷磚的正、反兩面都必須漆成同樣的顏色。有一天小可可突發(fā)奇想，覺得有必要試試看這些瓷磚究竟能漆成多少種本質不用的圖案。所謂兩種圖案本質不同就是其中的一種圖案無論如何旋轉、或者翻轉、或者同時旋轉和翻轉都不能得到另外一種圖案。78plya定理旋轉是將瓷磚三角形整體順時針旋轉120o或240o。79plya定理翻轉是將瓷磚三角形整體左右翻轉180o。80plya定理一開始，小可可覺得這項實驗很有意思，他知道n=1時有兩種不同的漆繪方案，n=2時也只有4種不同的漆繪方案，小可可還把這些方案畫了出來。81plya定理但是后來小可可發(fā)現(xiàn)n在變大的過程中，漆繪方案增長的速度很快，在n=14的時候，居然有676595096種不同的漆繪方案。這果然是一項非