原來(lái)簡(jiǎn)單的總結(jié)過(guò)polya定理：http://m.shnenglu.com/sdfond/archive/2009/05/12/82665.html
　　這里再次把一些polya定理的題目歸一下類(lèi)～
　　話(huà)說(shuō)ICPC的題目是越來(lái)越難，因?yàn)榻?jīng)典的算法大家都知道了，因此出題的方向只能是要么把模型隱藏的很深，要么就把一系列算法知識(shí)綜合起來(lái)考察，這個(gè)時(shí)候分析問(wèn)題的能力和靈活運(yùn)用知識(shí)的能力就顯得尤為重要。
　　polya定理在很久以前的ICPC題目中就已經(jīng)出現(xiàn)過(guò)，不過(guò)那個(gè)時(shí)候大家對(duì)于置換群都了解不多，因此polya定理算是很生僻的一個(gè)東西。然而人類(lèi)總是飛速的進(jìn)步，現(xiàn)在互聯(lián)網(wǎng)上鋪天蓋地的題解使得polya定理走出深閨，逐漸被廣大acmer所熟知。但是魔高一尺道高一丈，出題人也逐漸把polya定理的題出得越來(lái)越難做，越來(lái)越不好想，今天我就來(lái)總結(jié)一下這些頗有難度的polya定理題目(包括Burnside引理)。
　　polya定理主要就是解決一類(lèi)著色問(wèn)題，或者說(shuō)是同構(gòu)計(jì)數(shù)問(wèn)題。設(shè)染色方案數(shù)是n，置換群個(gè)數(shù)是p，置換群長(zhǎng)度是s，那么利用Burnside引理，通過(guò)考察每個(gè)染色方案和每個(gè)置換群，可以在O(nsp)時(shí)間復(fù)雜度計(jì)算出答案。polya定理巧妙的利用同一循環(huán)內(nèi)著色相同這個(gè)事實(shí)，避開(kāi)了枚舉著色方案，使得復(fù)雜度降到了O(sp)。但是利用polya定理的條件就是對(duì)于染色沒(méi)有限制，如果不滿(mǎn)足這個(gè)條件(比如對(duì)于不同循環(huán)節(jié)的染色限制，顏色數(shù)的限制等等)，就沒(méi)法直接使用polya定理。另一方面，同構(gòu)計(jì)數(shù)無(wú)論如何也無(wú)法避開(kāi)找置換群，因此很多題目也在這個(gè)上面做文章，把置換群弄得非常多，使得常規(guī)的枚舉無(wú)法滿(mǎn)足要求，必須尋求優(yōu)化解法。
　　這樣討論下來(lái)就可以把polya定理分成幾個(gè)等級(jí)，最簡(jiǎn)單的就是找出置換群，染色就行了，這類(lèi)代表題目有：
　　　　HOJ 2084 The Colored Cubes
　　　　HOJ 2647 Megaminx
　　　　POJ 1286 Necklace of Beads
　　　　POJ 2409 Let it Bead
　　　　HDU 1812 Count the Tetris
　　這些題目都是polya定理最基本的應(yīng)用，當(dāng)然以后估計(jì)再也見(jiàn)不到這樣的題目了，因?yàn)樘嗦懵懔恕?br>
　　第二個(gè)等級(jí)的題目難度就略微提升了一些，比如加入顏色限制，這樣就要用Burnside引理：
　　　　TJU 2795 The Queen's New Necklaces
　　這個(gè)題目就是對(duì)每種顏色的個(gè)數(shù)進(jìn)行了限制，不過(guò)因?yàn)橹脫Q群很有規(guī)律，我用的是多重集排列來(lái)計(jì)數(shù)的。
　　　　UVa 10601 Cubes
　　也是限制了顏色數(shù)，但是這個(gè)題里置換群比較沒(méi)規(guī)律，我是直接搜的。
　　　　UVa 11255 Necklace
　　和上面兩個(gè)題目類(lèi)似，我也是用排列組合直接數(shù)了，寫(xiě)起來(lái)有些麻煩，也許用dp更簡(jiǎn)單些。
　　　　POJ 2154 Color
　　這個(gè)題目是一個(gè)里程碑，它標(biāo)志著一類(lèi)題目的優(yōu)化方法。同樣是項(xiàng)鏈旋轉(zhuǎn)，因?yàn)橹脫Q群數(shù)量太多，利用數(shù)論的知識(shí)優(yōu)化。

　　第三個(gè)等級(jí)就比較變態(tài)了，幾乎沒(méi)有一看就能想出來(lái)的題目。這類(lèi)題目的特點(diǎn)是，非常綜合，用到了很多知識(shí)；有的題目難點(diǎn)甚至不在求解同構(gòu)計(jì)數(shù)的部分。
　　　　POJ 2888 Magic Bracelet 難度指數(shù)：★★★
　　一道很不錯(cuò)的題目，這里加入連接限制同時(shí)還考察優(yōu)化，優(yōu)化方法同上。連接限制如何處理？注意到項(xiàng)鏈個(gè)數(shù)很少，因此可以建圖，然后分別求出每種顏色連接n個(gè)珠子后回到自身的方案數(shù)，累加即可，這里可以用矩陣快速冪求解。
　　　　TJU 3352 Birthday Toy   難度指數(shù)：★★★
　　這個(gè)題目出得也很不錯(cuò)，同樣是加入鏈接限制，不過(guò)這里的連接限制很有規(guī)律性，是相鄰的珠子不可以染成同色，因此可以列出遞推關(guān)系，最后化簡(jiǎn)成公式求解。此外由于還是項(xiàng)鏈旋轉(zhuǎn)，用到了一樣的優(yōu)化方式(這個(gè)優(yōu)化方式已經(jīng)被考爛了)。
　　　　HDU 2481 Toy　　　　　　難度指數(shù)：★★★★
　　08年成都現(xiàn)場(chǎng)賽題目，難點(diǎn)在于求解遞推關(guān)系。這個(gè)題目比較新穎的地方在于不是染色了，而是同構(gòu)圖計(jì)數(shù)。首先由于圖形的特殊性可以推出遞推關(guān)系(不是很好想)，然后利用矩陣求解。此外這個(gè)題目把同一循環(huán)節(jié)的縮成了一個(gè)珠子，利用這用方式來(lái)考慮問(wèn)題，是一種新的思路。此外由于還是項(xiàng)鏈旋轉(zhuǎn)，用到了一樣的優(yōu)化方式(凡是跟項(xiàng)鏈有關(guān)的就沒(méi)有不考這個(gè)的了)。這個(gè)題目詳盡的題解在這里：http://hi.baidu.com/spellbreaker/blog/item/1a7d9902ff6844e409fa93fb.html
　　　　SGU 282 Isomorphism　　難度指數(shù)：★★★★★
　　這個(gè)題目比較新穎，置換非常多，因此需要一些巧妙的方法優(yōu)化。置換的個(gè)數(shù)達(dá)到了n!，但是可以通過(guò)搜索來(lái)枚舉每個(gè)循環(huán)節(jié)的長(zhǎng)度，把復(fù)雜度降到了求解n的分拆數(shù)方案數(shù)那么多。設(shè)n = L1 + L2 + ... + Lm，那么滿(mǎn)足這個(gè)類(lèi)型的置換個(gè)數(shù)是n! / (L1 * L2 * ... * Lm * k1! * k2! * ... * kt!)，其中t是不同的循環(huán)節(jié)長(zhǎng)度的個(gè)數(shù)，ki是每種循環(huán)節(jié)長(zhǎng)度，這個(gè)公式的大體思想就是：首先因?yàn)槭侵脫Q，因此每個(gè)循環(huán)節(jié)內(nèi)的數(shù)是固定的，把一個(gè)循環(huán)節(jié)內(nèi)的數(shù)看成1個(gè)就變成了多重集的排列，但是每個(gè)循環(huán)節(jié)(Li)內(nèi)，第一個(gè)數(shù)有(Li - 1)種選法(只要不是自己就行)，第二個(gè)數(shù)有(Li - 2)種選法，依次類(lèi)推，因此每個(gè)循環(huán)節(jié)還要乘以(Li - 1)!；之后因?yàn)閷?duì)于兩個(gè)同樣長(zhǎng)度的循環(huán)節(jié)，一旦選定了位置，其實(shí)不可以互換，因此要把多余的方案除掉，最后就是上述的公式。找出了置換的個(gè)數(shù)，接下來(lái)的問(wèn)題就是，因?yàn)轭}目是對(duì)邊染色，因此要把點(diǎn)置換映射成邊置換。通過(guò)小范圍的觀察可以發(fā)現(xiàn)(具體證明不太會(huì))：一個(gè)長(zhǎng)度為L(zhǎng)的點(diǎn)循環(huán)節(jié)對(duì)應(yīng)[L/2]個(gè)邊循環(huán)節(jié)，兩個(gè)長(zhǎng)度分別是L1、L2的點(diǎn)循環(huán)節(jié)對(duì)應(yīng)gcd(L1, L2)個(gè)邊循環(huán)節(jié)。因?yàn)閜olya定理同一循環(huán)節(jié)內(nèi)染色相同，因此不必關(guān)心對(duì)應(yīng)后的邊循環(huán)節(jié)長(zhǎng)度，只要知道個(gè)數(shù)即可(這一點(diǎn)很巧妙)，所以這樣映射便可以求出結(jié)果。最后要注意的是題目說(shuō)明了模一個(gè)素?cái)?shù)，因此可以預(yù)處理出逆元來(lái)。
　　　　SPOJ 422 Transposing is Even More Fun　　　　難度指數(shù)：★★★★★
　　這個(gè)題目需要一些觀察力。把地址轉(zhuǎn)置之后對(duì)應(yīng)的寫(xiě)下來(lái)，會(huì)發(fā)現(xiàn)，一個(gè)長(zhǎng)度為L(zhǎng)循環(huán)節(jié)只需要移動(dòng)L-1次(利用一個(gè)元素進(jìn)行對(duì)換)，這樣假設(shè)有k個(gè)循環(huán)節(jié)，那么答案就是2 ^ (a + b) - k，關(guān)鍵問(wèn)題是如何求k。循環(huán)節(jié)的個(gè)數(shù)其實(shí)就是相當(dāng)于地址右移若干個(gè)b位后本質(zhì)不同的地址個(gè)數(shù)，這樣就劃歸到了polya定理的范疇。長(zhǎng)度為a+b的地址一共可以右移(a + b) / (a, b)次(之后就出現(xiàn)循環(huán)了)，因此這就是置換的個(gè)數(shù)。現(xiàn)在分別考慮每個(gè)置換下不同的地址個(gè)數(shù)，設(shè)g = gcd(a, b)，那么可以看成一共有(a + b) / g個(gè)珠子，每個(gè)大小是2 ^ g，這樣如果移動(dòng)i下，那么對(duì)應(yīng)的本質(zhì)不同的地址個(gè)數(shù)是(2 ^ g) ^ gcd(i, (a + b) / g)多個(gè)(類(lèi)似于項(xiàng)鏈旋轉(zhuǎn))，最后累加然后除以總置換數(shù)即可。
　　然后的問(wèn)題就是如何高效求解，由于數(shù)據(jù)組數(shù)非常多，利用歐拉函數(shù)以O(shè)(sqrt(a + b))的復(fù)雜度依然TLE。后來(lái)參照cyx的論文，實(shí)現(xiàn)了一個(gè)理論復(fù)雜度看似很高但是實(shí)際很快的方法。記f[i]表示滿(mǎn)足gcd(i, (a + b) / g)是i的個(gè)數(shù)，先把總數(shù)分配給1，然后對(duì)(a + b) / g因式分解，用類(lèi)似bfs的方法，擴(kuò)展當(dāng)前狀態(tài)，如果從x擴(kuò)展到了xp，那么就把x總數(shù)的1/p分給xp，注意不要重復(fù)擴(kuò)展，利用一個(gè)單調(diào)隊(duì)列讓每個(gè)和數(shù)都唯一的被它的最小素因子擴(kuò)展一次即可。這個(gè)方法復(fù)雜度難以估計(jì)但是很快出解。

注：本文作于2009年9月25日10點(diǎn)整