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

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

2、個數(shù)都相等的字符串還有：aacb,baca等，因為他們也是含有兩個 a ,一個 b ,一個 c 。所有滿足這個性質(zhì)的字符串按字典順序排列后，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)外的洞躲藏。擴展歐幾里德算法w 下面，我

3、們對歐幾里德算法進行推廣，使得該算法不僅能得出任意兩個正整數(shù)a和b的最大公約數(shù)d，而且還能計算出滿足下式的整系數(shù)x和y。w D=gcd(a,b)=ax+by(x和y可能為0或負數(shù))擴展歐幾里德wFunction euclid(a,b:longint; var x,y:longint):longint;wVar t:longint;wBeginw if b=0 then w beginw euclid:=a; x:=1; y:=0;w endwElsew beginw euclid:=euclid(b,a mod b,x,y);w t:=x; x:=y; y:=t-(a div b)*y;w e

4、nd;wEnd;擴展歐幾里德算法w 上述函數(shù)是從歐幾里德算法中衍生出來的。算法一開始，它首先測試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。解的個數(shù)w 已

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

6、數(shù)的測試w 剛剛接觸信息學的時候，可能就做過關于素數(shù)測試的題目，當時的方法是2-sqrt(n)的枚舉，這樣的效率并不高。w 歐拉定理：a(n) 1(mod n)，其中(n) 是n的歐拉函數(shù)，(n) 不大于n的但與n互質(zhì)的正整數(shù)個數(shù)。a可以取任意值。w 易知，(素數(shù)n)=n-1 費爾馬小定理w 從而，當n是質(zhì)數(shù)的時候，an1 1(mod n)，這是歐拉定理的特殊情況，也稱為費爾馬小定理。w 那么，費爾馬小定理的逆定理是否成立呢？答案是否定的，但是這種情況很少。也就是說，對于a取1n-1的任意一個值的時候，都有an1 1(mod n)成立的話，則幾乎可以可定地確認n是素數(shù)。費爾馬小定理w 當a=2

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

8、+12=22 3+7+19=29 w 7+12+19=38 3+12+19=34選數(shù)w 現(xiàn)在，要求你計算出和為素數(shù)共有多少種。w 輸入格式為：w n,k (1n20，kn)w x1,x2,xn (1xi5000000)w 一個整數(shù)(滿足條件的種數(shù))。w 樣例輸入：4 33 7 12 19w 樣例輸出：1選數(shù)w 這一題采取的是搜索的算法，這已經(jīng)是十分低效的了，但是還得加上素數(shù)判定的復雜度，所以這里采取費爾馬小定理的逆定理判定素數(shù)才能使得整個程序在短時間內(nèi)出解。小結(jié)w 關于數(shù)論的一些知識本人還十分缺陷，所以只能做一些簡單知識的介紹。矩陣的簡單運用by 韓文弢w 由m行、n列的標量所構(gòu)成的數(shù)組被稱為

9、一個mn的矩陣(matrix)。w 一般用大寫字母表示矩陣，對應的小寫字母表示矩陣中的項(entry)。w 這里，aij就是矩陣A中第i行第j列的項。654321232221131211aaaaaaA矩陣的乘法w 設A=(aij)mn,B=(bij)np是兩個矩陣，矩陣C=AB，則C是一個mp的矩陣，且其中第i行第j列的項的值為A中第i個行向量與B中第j個列向量的內(nèi)積。w 也就是說，nkkjikijbac1矩陣乘法舉例121310140212A101012130241B)(ijcABC60402) 1 , 2, 0 , 1 ()0 , 2 , 1 , 2(11c30238)0 , 1, 3,

10、4()0 , 2 , 1 , 2(12c30014) 1 , 0 , 1 , 2()0 , 2 , 1 , 2(13c81388135336C矩陣乘法的應用w 求無權圖中長度為k的路徑數(shù)123450010000101110100010101010Adj11010120200030212020002022Adj矩陣乘法運算的性質(zhì)w 不滿足交換律nAB=BA不一定成立w 滿足結(jié)合律n(AB)C=A(BC)成立w 滿足分配律nA(B+C)=AB+AC成立（左分配律）n(A+B)C=AC+BC成立（右分配律）例題1：遞推數(shù)列(recurrence)1k100，0n1,000,000例題1樣例w 輸入樣

11、例2 101 11 1w 輸出樣例89遞推數(shù)列解答wFibonacci數(shù)列遞推公式：fi=fi-1+fi-2w另外再設一個矩陣A，使得w容易看出，w即，121,iiiiffFffFAFF 0111A2110111iiiiffff遞推數(shù)列解答（續(xù)）w 設w 則有w 如何降低復雜度？w 時間復雜度：nO(logn)iiiffF100,11FAFFii分治！遞推數(shù)列解答（續(xù)）w 推廣到一般情況，w 其中，w 時間復雜度：nO(k3logn)021,FAFfffFiiikikii010000100001321kaaaaA例題2：圖形變換(shape)1n10,000，1m10,000例題2樣例w 輸入

12、樣例4 1M 0 1Z 0.5R 45F 02 1w 輸出樣例0.0000 -1.4142圖形變換解答w 直觀算法：直接模擬n時間復雜度：O(mn)n太慢了！w 改進算法：矩陣運算n時間復雜度：O(m+n)n很好！w 實際應用n三維圖形處理小結(jié)w 線性代數(shù)是一件十分有力的數(shù)學工具。w 一般地，矩陣乘法可以用來解決大量線性關系的計算，能夠把問題大大簡化。 w 而線性方程組則是解決自然科學問題的常用工具，可以用矩陣的基本操作來求解。 w 涉及思想：n分治思想n轉(zhuǎn)化思想n消元思想棋盤多項式和任務分配w 任務分配w 有N位工作人員，同時有N項任務，每人必須承擔一項任務，若給出某人不能從事的某些任務，問

13、要安排好工作，共有多少種方案？w N20s很大程序2（分）2s大程序3（參）0.5s小小結(jié)w 棋盤多項式在信息學競賽中的運用不是很廣泛，似乎只能解決任務分配一類的問題。這里做一個了解即可。置換群與plya定理w 先看一個例題：w 有n個人，按1n編號。每個人手里都拿著一個球，這些球也按1n編號。但是1號選手手里拿的不一定是1號球，所以他們可以兩兩相互交換手里的球，使得最終i號選手手里的是i號球。請問如果交換可以同時進行，那么最少需要多少個單位時間（兩兩交換一次是一個單位時間），最少又需要多少次交換？置換群w 在解決這個問題之前，需要先學習一些群論，特別是置換群的知識。這里只介紹一些結(jié)論。w 將

14、每個人編號和所拿的球的編號一一對應起來寫成如下形式：w 這稱為一個置換群。w 如果把i和j下面的元素交換，稱為一次置換。an . a3 a2 a1n . 3 2 1置換群w 例如 (1 2 3 4)w (3 4 1 2)w 這是一個置換群。下面進行一種操作，在第一行中找到1，然后看1下面的元素，是3，然后在第一行中找3，3下面的元素是1。這樣我們找出了13找個循環(huán)節(jié)，寫成：(1 3)w (3 1)w 然后找2，2下面的元素是 4，接著4下面的元素又是2，所以又找出了一個循環(huán)節(jié)(2 4)w (4 2)置換群w 在這里，13的循環(huán)節(jié)和24的循環(huán)節(jié)被成為輪換。一個置換群可以寫成若干個輪換的乘積：w

15、(1 2 3 4)(1 3)(2 4)w (3 4 1 2) (3 1) (4 2)w 再來看看題目，根據(jù)題目給出的信息，可以構(gòu)造出一個置換群，在該置換群中，可以分解出若干個輪換。試想如果交換在不同的輪換內(nèi)進行，也就是輪換1中的元素和輪換2中的元素交換。這樣必定不會達到最優(yōu)的交換次數(shù)（為什么？）。所以對于每一個輪換，我們可以分別進行處理。置換群w 由于每個輪換都是一個循環(huán)，他們的本質(zhì)是相同的，也就是我們可以對輪換中的元素進行重新的編號。于是一個長度為n的輪換可以寫成如下形式：w (1 2 3 n-1 n)w (2 3 4 n 1)w 問題現(xiàn)在已經(jīng)一般化了，長度為n的輪換，最少需要多少個單位時間

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

17、個單位的交換時間，其他任何情況都只需要2個單位的交換時間就可以了。書架w 書架w 書架上有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)。這樣的交換可以使得代價值之和最小。無聊的排序w 仍然考慮輪換的問題。在一個輪換中，利用任意一個元素和其他元素交換，可以使得所有元素歸位。那么我們選取輪換中最小的那個元素，然后和別的元素進行交換，這樣可以使得交換的代價值之和“最小”。w 但是這個代價值一定最小的嗎？為什么要只能在輪換內(nèi)進行交換呢？會不會和輪

18、換外的元素交換之后，能使代價值更小呢？w 答案是肯定的！可以利用輪換外的元素。無聊的排序w 舉個例子：w (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)。這樣的操作可以使得代價值更加小。所以在對一個輪換進行處理的時候，應該考慮兩種交換方式，選擇更優(yōu)秀的交換方式進行。plya定理w plya定理是用來解決一般染色問題的有效方法。w 例如給出

19、一個三角形，要求你對三角形的邊和點進行染色，有m種顏色可以供你選擇，每條邊和每個點必須染色。問你經(jīng)過翻轉(zhuǎn)旋轉(zhuǎn)等操作后，仍然本質(zhì)不同的三角形個數(shù)有多少種。plya定理w 對頂點和邊進行標號，例如一個正三角形可以這樣標號：w 把本質(zhì)不用的旋轉(zhuǎn)翻轉(zhuǎn)操作，用置換群表示。例如向右旋轉(zhuǎn)60o的操作可以表示成w (1 2 3 4 5 6)w (3 1 2 6 4 5)w 表示1的地方被3代替，2的地方被1代替。plya定理w 假設可以列出k個置換群，且在第i個置換群中輪換的個數(shù)為fi，偉大的數(shù)學家plya研究出了一個讓人興奮的結(jié)論：用m種顏色對圖形進行染色，本質(zhì)不同的染色方案數(shù)為(mf1+mf2+mfk)/

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