如何統計n階環染成m種顏色，任意長度為m的相鄰區域不同時出現所有顏色的方案數

1樓：misaka

不知道這個問題還要不要考慮原題裡面的旋轉意義下本質不同的條件。

先考慮沒有本質不同這個條件的情況，令表示長度為的環的答案。

遞推求解，假設我們已經有了初值。遞推的過程可以看作往長度為的環中插入乙個節點，並且前後狀態都要滿足任意長度為的相鄰區域不同時出現所有顏色。由此可見，插入節點的顏色限制只與插入位置兩側的若干個節點顏色有關。

對於任意的，這個遞推過程都是相同的，所以這個遞推是乙個常係數線性遞推。但是這個遞推的係數很難直接推導得出，可以先計算出前幾項，然後利用BM演算法求出係數。

考慮使用dp來求解前幾項，設狀態表示長度為的鏈，鏈頭的個節點的顏色狀態為，鏈尾的個節點的顏色狀態為的滿足條件的鏈的數量，狀壓dp一下即可。最後長度為的環可以由長度為的鏈首尾相連得到，連線的時候check一下鏈頭和鏈尾在拼接後的對應那一部分是否滿足條件，滿足條件就計入。

這樣就求出了初值和遞推係數，接下來的常係數線性遞推用矩陣快速冪來求解即可，或者再用特徵多項式進一步優化快速冪，可以得到更低的複雜度。

再考慮有本質不同這個條件的情況，看到這個本質不同的條件，可以立刻聯想到使用Polya定理來求解，但是這裡還有乙個附加條件，而不是簡單的使用個顏色染色，Polya定理無法使用，故而嘗試更一般的Burnside引理。

類似推導Polya定理的過程，考慮環的旋轉對應的置換的迴圈個數。設其旋轉的角度為，起點為，其至少旋轉次後才能與起點重合。

於是有，即，求得。

所以置換的迴圈個數為，不動點個數也就為。

故總方案數為，因為，還需要進一步優化。

對分解質因子，列舉因子即可。