pálya計數(shù)法的應(yīng)用

1、Plya計數(shù)法的應(yīng)用編輯課件問題描述06年江蘇上海選拔賽染色圖是無向完全圖，且每條邊可被染成k種顏色中的一種。兩個染色圖是同構(gòu)的，當且僅當可以改變一個圖的頂點的編號，使得兩個染色圖完全相同。問N個頂點，k種顏色，本質(zhì)不同的染色圖個數(shù)（模質(zhì)數(shù)NP109）。N53編輯課件123123123問題描述編輯課件123312132問題描述編輯課件問題描述N=3 K=2123123123123編輯課件簡單分析枚舉會超時普通的乘法原理無法求解編輯課件Burnside引理設(shè)G是置換群，C是G的著色集合。C中的不等價著色數(shù)為：使著色通過G中的置換保持不變的著色的平均數(shù)。編輯課件Plya定理假設(shè)有k種不同的顏色，某

2、個置換的循環(huán)數(shù)為c，則對于這個置換，通過它保持不變的著色數(shù)為，k的c次方。編輯課件例題分析放在這個問題中，置換群中的對象就是所有的邊，染成k種顏色，G就是由點的置換引起的邊的置換的群。編輯課件分析例如N=3時一共有3條邊。點的不同排列有3!=6種。由點的置換而引起的對應(yīng)的邊的置換如下：編輯課件編輯課件123312編輯課件分析先求出每個置換的循環(huán)數(shù)c根據(jù)Plya定理，可求出本質(zhì)不同的方案數(shù)：編輯課件分析這個算法十分直觀，直接套用了Plya定理，但需要枚舉每個對于點的置換，并求循環(huán)數(shù)。時間復(fù)雜度為 O(N!N2)。對于本題N53的數(shù)據(jù)范圍，這個算法會超時。編輯課件分析再進一步分析問題，會發(fā)現(xiàn)，其實

3、這N!個置換中，有許多是類似的，比如：編輯課件編輯課件分析觀察這些對于點的置換，發(fā)現(xiàn)它們都是由一個長度為1和一個長度為2的循環(huán)組成。顯然它們對應(yīng)的邊的置換，也是類似的。如果把每個置換都處理一遍，是很浪費的。這3個，只要處理一個即可。編輯課件分析枚舉出所有本質(zhì)不同的對于點的置換，并對每種置換求下面2個值1、該種置換的對應(yīng)邊的置換的循環(huán)節(jié)數(shù)2、與該種置換類似的置換總數(shù)編輯課件分析要保證枚舉出來的對于點的置換各不相同，只需枚舉它的所有循環(huán)節(jié)長度，設(shè)為Li，并保證0L1L2Lm L1+L2+Lm=N N=53時，一共要需要枚舉329921種不同情況。編輯課件分析然后需要把對應(yīng)點的循環(huán)信息轉(zhuǎn)化成對應(yīng)邊的

4、置換的循環(huán)節(jié)數(shù)編輯課件分析假設(shè)點i與點j同屬于一個長度為L的循環(huán)中，則 (i,j)組成的置換中循環(huán)節(jié)個數(shù)為有一個長度為5的循環(huán)(1,2,3,4,5) (1,2),(2,3),(3,4),(4,5),(5,1)(1,3),(2,4),(3,5),(4,1),(5,2)編輯課件分析假設(shè)點i與點j各屬于長L1和L2的兩個不同循環(huán)中，則這樣的邊(i,j)組成的置換中循環(huán)節(jié)個數(shù)為(L1,L2)。(1,2) (3,4,5,6) (1,3),(2,4),(1,5),(2,6)(1,4),(2,5),(1,6),(2,3) 編輯課件分析還需要求出與其類似的置換數(shù)假設(shè)已確定了0L1L2Lm ，接下來就是將1N這

5、N個點分別放入這m個循環(huán)節(jié)中，滿足第i個循環(huán)中恰含有Li個點，這相當于m個圓排列問題，可知一共有 種不同方式。編輯課件分析如果有Li=Li+1=Lj，那么每(j-i+1)!種方案又是重復(fù)的，所以還要除以(j-i+1)!編輯課件分析所以總的置換個數(shù)就是每個循環(huán)的長度為L每組Li=Li+1=Lj s為j-i+1編輯課件分析需要計算很多T2-1，其中T2很大，而且是-1次的，難道要分解質(zhì)因數(shù)了嗎？P是質(zhì)數(shù)，且滿足NP。所以T2也與P互質(zhì)由數(shù)論知識可知：T2p-11 (mod p)T2-1 T2p-1T2-1=T2p-2 (mod p)所以可以把T2-1轉(zhuǎn)化為求T2p-2，可用倍增的方法在O(Logp

6、) 的時間內(nèi)求解。編輯課件本題總結(jié)這個問題遇到了這樣的困難：置換的個數(shù)偏多而導(dǎo)致不能對每個置換都算其循環(huán)數(shù)解決的方法，就是找出置換群中相似的置換，而不重復(fù)計算這個去除冗余運算的方法在Plya計數(shù)問題中經(jīng)常用到對于每類相似置換個數(shù)的計算，也需要扎實的數(shù)學(xué)功底。編輯課件全文總結(jié)信息學(xué)競賽中經(jīng)常出現(xiàn)這類問題。比如Transportation is fun (spoj 419)Hes Circles (sgu 294)Cubes (uva 10601)它們在直接使用公式時往往會遇到一些困難。這些困難雖然不同，但也有一些相似之處。編輯課件全文總結(jié)Plya計數(shù)法不僅僅能解決許多計數(shù)問題，它的證明過程也是相

7、當有意思的。靈活使用Plya計數(shù)法，不僅僅需要熟練掌握此類問題的性質(zhì)，還要有扎實的數(shù)學(xué)功底和分析問題能力。數(shù)學(xué)方法是解決問題的工具，而分析問題能力是算法的源泉。編輯課件謝謝大家!編輯課件分析下面討論一下如何計算：一部分是MT1，其中T1并不大，MT1 mod P可以用倍增的思想在log(T1)時間內(nèi)計算。編輯課件證明設(shè)c為 中的一種著色，那么與 c 等價的著色數(shù)等于G中的置換個數(shù)除以 c 的穩(wěn)定核中的置換個數(shù)。編輯課件證明定理1：對于每一種著色c，c的穩(wěn)定核G(c)是一個置換群，而且對 G 中任意置換f與 g，g*c=f*c 當且僅當 f-1 g 屬于 G(c)。編輯課件證明假設(shè)f*c=g*c

8、 則所以 f-1 g使c不變，因此，f-1 g 屬于G(c)。反之，假設(shè)f-1 g屬于G(c) ，通過類似的計算可證得f*c=g*c編輯課件證明推論：設(shè)c為 中的一種著色，那么與 c 等價的著色數(shù)等于G中的置換個數(shù)除以 c 的穩(wěn)定核中的置換個數(shù)。編輯課件證明設(shè) f 是 G 中的一個置換，根據(jù)定理1，滿足g*c=f*c的置換 g 實際上就是 中的那些置換。 由消去律，則從f h=f h得到h=h。集合中 的置換個數(shù)等于G(c)中置換的個數(shù)。 因為總共有|G|個置換，所以，與c等價的著色數(shù)等于 編輯課件證明我們要數(shù)使f保持c不變即f*cc的對偶(f,c)的個數(shù)。 編輯課件證明一種計數(shù)的方式是考察G中的每個f ，并計算f保持著色不變的著色數(shù)，然后相加所有的量。設(shè)D(f)是通過f保持著色不變的著色集，所以用這種方式計數(shù)得到 編輯課件證明另一種計數(shù)的方式按等價類將著色歸類。在同一等價類中，兩種著色對和貢獻了同樣的量，每個等價類的總貢獻是