原來簡單的總結(jié)過polya定理：http://m.shnenglu.com/sdfond/archive/2009/05/12/82665.html
　　這里再次把一些polya定理的題目歸一下類～
　　話說ICPC的題目是越來越難，因為經(jīng)典的算法大家都知道了，因此出題的方向只能是要么把模型隱藏的很深，要么就把一系列算法知識綜合起來考察，這個時候分析問題的能力和靈活運用知識的能力就顯得尤為重要。
　　polya定理在很久以前的ICPC題目中就已經(jīng)出現(xiàn)過，不過那個時候大家對于置換群都了解不多，因此polya定理算是很生僻的一個東西。然而人類總是飛速的進(jìn)步，現(xiàn)在互聯(lián)網(wǎng)上鋪天蓋地的題解使得polya定理走出深閨，逐漸被廣大acmer所熟知。但是魔高一尺道高一丈，出題人也逐漸把polya定理的題出得越來越難做，越來越不好想，今天我就來總結(jié)一下這些頗有難度的polya定理題目(包括Burnside引理)。
　　polya定理主要就是解決一類著色問題，或者說是同構(gòu)計數(shù)問題。設(shè)染色方案數(shù)是n，置換群個數(shù)是p，置換群長度是s，那么利用Burnside引理，通過考察每個染色方案和每個置換群，可以在O(nsp)時間復(fù)雜度計算出答案。polya定理巧妙的利用同一循環(huán)內(nèi)著色相同這個事實，避開了枚舉著色方案，使得復(fù)雜度降到了O(sp)。但是利用polya定理的條件就是對于染色沒有限制，如果不滿足這個條件(比如對于不同循環(huán)節(jié)的染色限制，顏色數(shù)的限制等等)，就沒法直接使用polya定理。另一方面，同構(gòu)計數(shù)無論如何也無法避開找置換群，因此很多題目也在這個上面做文章，把置換群弄得非常多，使得常規(guī)的枚舉無法滿足要求，必須尋求優(yōu)化解法。
　　這樣討論下來就可以把polya定理分成幾個等級，最簡單的就是找出置換群，染色就行了，這類代表題目有：
　　　　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)然以后估計再也見不到這樣的題目了，因為太赤裸裸了。

　　第二個等級的題目難度就略微提升了一些，比如加入顏色限制，這樣就要用Burnside引理：
　　　　TJU 2795 The Queen's New Necklaces
　　這個題目就是對每種顏色的個數(shù)進(jìn)行了限制，不過因為置換群很有規(guī)律，我用的是多重集排列來計數(shù)的。
　　　　UVa 10601 Cubes
　　也是限制了顏色數(shù)，但是這個題里置換群比較沒規(guī)律，我是直接搜的。
　　　　UVa 11255 Necklace
　　和上面兩個題目類似，我也是用排列組合直接數(shù)了，寫起來有些麻煩，也許用dp更簡單些。
　　　　POJ 2154 Color
　　這個題目是一個里程碑，它標(biāo)志著一類題目的優(yōu)化方法。同樣是項鏈旋轉(zhuǎn)，因為置換群數(shù)量太多，利用數(shù)論的知識優(yōu)化。

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

注：本文作于2009年9月25日10點整