給 定一個N 個結點的無向完全圖（ 任意兩個結點之間有一條邊）， 現在你可以用 M 種顔色對這個圖的每條邊進行染色，每條邊必須染一種顔色。 若兩個已染色的圖，其中一個圖可以通過結點重新編号而與另一個圖完全相同， 就稱這兩個染色方案相同。 現在問你有多少種本質不同的染色方法，輸出結果 mod P。P 是一個大于N 的質數。 僅一行包含三個數，N、M、P。 僅一行，為染色方法數 mod P 的結果。 3 4 97 20 資料範圍：1≤N≤53，1≤M≤1000，N
【分析】
關于這題，這文檔講得很清楚：http://wenku.baidu.com/view/fee9e9b9bceb19e8b8f6ba7a.html?from=search###
這題想起來挺難的。
首先它是對點的置換，但是是邊染上了顔色，就是說實際上是邊的置換。是以我們要看一下點置換和邊置換之間的關系。
假定一個點置換，把它表示為循環，比如是(a1,a2,....)(b1,b2...)(c1,c2...)...
1、對于不在一個循環裡面的點：
比如a1,b1, 那麼會有邊循環((a1,b1),(a2,b2)...) 設a循環的循環節是l1,b循環的循環節是l2,那麼形成的邊循環的循環節顯然是LCM(l1,l2)。
一共有l1*l2個點對，每個點對都在一個循環節為LCM(l1,l2)的循環上，是以一共有l1*l2/LCM(l1,l2)=GCD(l1,l2)個循環節，是以C(f)=m^GCD(l1,l2)。（回到burnside引理，C為置換之後仍為本身的數目，就是說要循環節裡的每條邊都一樣的顔色）
2、對于在一個循環裡面的點：
比如a1、a2。設這個a循環的循環節為l1。
如果l1是奇數，那麼循環長度為l1，一共有C(l1,2)個點對，是以是(l1-1)/2個循環節，是以C(f)=m^((l1-1)/2)。
如果l1是偶數，除了上面這種情況之外，還有一種的循環節是l1/2（就是兩個點剛好相隔半個周期，而邊是雙向的），是以一共有(C(l1,2)-l1/2)/l1+1=l1/2個點對。
整理一下：
是以代碼很簡單，隻要枚舉n的拆分，然後計算不動點就好了。這裡有用到逆元，p是質數可以用費馬小定理。
分母上面先乘完再求逆元，我就是一邊乘一邊逆元就逾時了。。。ORZ。。。
View Code
2017-01-12 11:34:31