題意：
? ? ? 給你一串珠子（連接成了一個環），共有n個珠子組成，你有t種顏色，現在你來給這個珠子染色，問染成項鏈有多少種方法？染成手鐲有多少種方法？在項鏈里，經過順時針旋轉后相同的算一個，在手鐲里，經過順時針旋轉或者沿著對稱軸兌換后一樣的算一個。


思路：
? ? ? 比較典型的等價類計數問題，我們定義兩個變量，a是旋轉的總個數，b是翻轉的總個數，那么根據Burnside和Polya定理，a = C[0] + C[1] + C[2] +..+C[n-1];
C[i]表示的是順時針移動i個后的種類數，C[i] = t^w,t是顏色種類，w是循環節個數，在這個題目里，旋轉是的循環節個數為gcd(i ,n);至于為什么可以自己想，想不通的話可以想想杭電上那個切蛋糕的題目，那么C[i] = t^gcd(i ,n)這樣就能求出各個C[i]然后求出a,此時的相連的答案已經出來了，就是a/n，那么b呢？b可以分情況討論，如果n是奇數那么對角線一共有n條，每次可以分出來(n+1)個循環節，那么b = n * t ^ ((n + 1)/2)如果n是偶數的話有兩種情況，不穿過任何點的為 n/2*t(n/2) 穿過兩個點的對角線為n/2*(n/2+1)那么此時的b=n/2*(t^(n/2) + t^(n/2+1)),那么手鐲的種類為(a+b)/(n*2).


這里在解釋下上面的那兩個定理，那兩個定理是求等價類計數問題的常用定理，大體意思就是說種類數等于所有可能置換方法的方法數的平均數，而每一個置換方法的個數等于顏色個數的循環節次冪，循環節就是置換里面的那個循環節。


#include<stdio.h>


long long gcd(long long a ,long long b)
{
? ?return a % b == 0 ? b : gcd(b ,a % b);
}




int main ()
{
? ?long long pow[60];
? ?long long n ,t ,i;
? ?long long a ,b;
? ?while(~scanf("%lld %lld" ,&n ,&t))
? ?{
? ? ? pow[0] = 1;
? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? pow[i] = pow[i-1] * t;
? ? ? a = 0;
? ? ? for(i = 0 ;i < n ;i ++)
? ? ? a += pow[gcd(i ,n)];
? ? ? if(n & 1) b = n * pow[(n+1)/2];
? ? ? else b = n / 2 * pow[n/2] + n / 2 * pow[n/2 + 1];?
? ? ? printf("%lld %lld\n" ,a / n ,(a + b) / n / 2);
? ?}
? ?return 0;
} ? ??

總結

以上是生活随笔為你收集整理的UVA10294项链和手镯（等价类计数问题）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。