求：用C种颜色染N阶完全图的不同染色方案(mod P),P为素数（两个染色方案是相同的当且仅当顶点编号重排后各边的颜色相同），
其中1<=N<=53,1<=C<=1000;

很明显这个群有N!个置换（顶点的排列）,一个置换可表示为 (a1,a2,……,am)(b1,b2,……,bn)(c1,c2,……,ck) ……循环节的形式，其中m+n+k=N。以下证明：
 
1： 在一个置换下，关联的顶点都在某个L长的循环节的边，可分成一共floor(L/2)个等价类。
2：在一个置换下，关联的顶点分别在两个长度为L1,L2的循环节内的边，可分成一共gcd(L1,L2)个等价类。

证明1： 在下面的证明中[x] 表示 (x mod L)

由于边{a[i],a([i]+[k])},{a[j],a([j]+[k])} ([k]>=1 && k<=L-1)在同一个等价类 ，而且 {a[i],a([i]+[k])} 与 {a[i],a([i]+[L-k])}在同一个等价类，所以
[k]={1,2,3,……,floor(L/2)} 和 [k]={L-1,L-2,……,ceil(L/2)}分别对应同一个等价类。所以1得证。

证明2：

若v1属于{a1,a2,……,am},v2属于{b1,b2,……,bn},则{v1,v2}的等价边为 {v1+[t],v2+[t]},其中,在t从 1开始增加的过程中，首次出现v1==v1+[t] && v2==v2+[t] 是在 t=lcm(m,n)的时候，所以每一条边共有lcm(m,n)条等价边，所以共有 m*n/lcm(m,n)个等价类 即为 gcd(m,n);

如果一个置换可以表示为 长度分别为 L1,L2,……,Lk(非降序排列)的k个循环节，那么在这个置换下边共有 n=Sum(floor(Li/2) ) + Sum(gcd(Li,Lj))个置换群;
而 k1*L1+k2*L2+k3*L3+……km*Lm=N(其中 Li != Lj for i != j) 的置换共有
 (N! *( (L1-1)! )^k1 *( (L2-1)!)^k2 *……* ((Lm-1)!)^km  )    /   (  ( (L1!)^k1 * (L2!)^k2 * (L3!)^k3*……(Lm!)^km )*  (k1! * k2! * k3!*……*km!)  )
即为 tot = N!/( (L1^k1)*(L2^k2)*(L3^k3)*……(Lm^km) * (k1! * k2! * k3! * …… *km!));
所以可以表示成这个形式(k1*L1+k2*L2+k3*L3+……+km*Lm)的固定构型个数为 ans= n* pow (C,tot)  个。

  1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 const int max_n=60;
 7 typedef long long LL;
 8 
 9 int N,C,P;
10 
11 LL facv[max_n],inv[max_n];
12 
13 LL mypow(LL a,LL b){
14     LL res=1,radix=a%P;
15     while(b){
16         if(b&1){
17             res*=radix;    res%=P;
18         }    
19         radix*=radix;    radix%=P;
20         b>>=1;
21     }
22     return res;
23 }
24 
25 LL cal_inv(int i){
26     return mypow(i,P-2);
27 }
28 
29 int gcd(int i,int j){
30     if(j==0)    return i;
31     return gcd(j,i%j);
32 }
33 void ini(){
34     facv[1]=1;
35     inv[1]=1;
36     for(int i=2;i<=N;i++){
37         inv[i]=cal_inv(i);
38         facv[i]=facv[i-1]*inv[i];    facv[i]%=P;
39     }
40 }
41 
42 int factor[max_n][2];    LL ans;
43 
44 void search(int sum,int top){
45     if(sum==N){
46         LL n=1;    
47         for(int i=1;i<=top;i++){
48             int len=factor[i][0],cnt=factor[i][1];
49             n*=mypow(inv[len],cnt); n%=P;            
50             n*=facv[cnt];    n%=P;
51         }
52         LL tot=0;
53         for(int i=1;i<=top;i++){
54 
55             int len=factor[i][0],cnt=factor[i][1];
56             tot+=cnt*(len/2);            //the same circle
57             tot+=cnt*(cnt-1)/2*len;        //two different circle
58 
59             for(int j=i+1;j<=top;j++){
60                 int len_j=factor[j][0],    cnt_j=factor[j][1];
61                 tot+=(cnt*cnt_j*gcd(len_j,len));
62             }
63         }
64         ans+=(n*mypow(C,tot))%P;    ans%=P;
65         return;
66     }
67     if(sum+factor[top][0]>=N){
68         return;
69     }
70     for(int i=factor[top][0]+1;i<=N-sum;i++){
71         for(int j=1;sum+i*j<=N;j++){
72             factor[top+1][0]=i;    factor[top+1][1]=j;
73             search(sum+i*j,top+1);
74         }
75     }
76 }
77 int main()
78 {
79     while(scanf("%d%d%d",&N,&C,&P)!=EOF){
80         ini();
81         factor[0][0]=0;
82         ans=0;
83         search(0,0);
84         printf("%lld\n",ans);
85     }
86     return 0;
87 }
88