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

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

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

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

<cite id="seggy"></cite>